#P6962. [2018年5月雅礼集训]⽣⽇聚会

    ID: 6793 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>难度分类提高+/省选-动态规划线性 DP数论倍数枚举排序与序列处理前后缀最值离线与分治离线查询构造与建模逆向思考CF2300

[2018年5月雅礼集训]⽣⽇聚会

生日聚会

题目背景

Brunhilda 就快要 7 岁了。今年她决定在拉脱维亚过生日。拉脱维亚位于东欧波罗的海沿岸,有欧洲北部巴黎之称。首都里加建筑美轮美奂,而远离首都的小镇更是自然风光无限好,休闲时间她也去野外、海边、山地露营游玩。现在,她正在筹备她的 7 岁生日 party。

问题描述

Brunhilda 发明了如下的游戏:所有的小朋友围成一圈跑动起来,直到听到数字 k。接着,所有的小朋友都互相抱紧尽量使自己在一个人数正好为 k 的小组中。只要剩下的小朋友个数至少有 k 个,那么就一定会形成一个新的 k 个小朋友的小组。最后,会留下少于 k 个小朋友,那么这些小朋友就会被淘汰。出于 Brunhilda 对骑士盔甲的喜爱,最后所有的小朋友都会被淘汰。一 旦小朋友全部被淘汰了,这轮游戏也就结束了。

Brunhilda 叫她的爸爸 Wotan 帮忙报数字。Wotan 并没有表现出对这个游戏多大的喜爱,于是在一开始就报出了 ∞\infty。Brunhilda 觉得在 party 上出现这样的状况实在是太尴尬了,于是她给了她的爸爸一些质数,要他每次报数时从中间选择一个数字。爸爸可以使用同一个数字多次。也就是说,当前有 nn 个小朋友时,报数 kk 后淘汰 n mod kn\bmod k 人,留下 k⌊n/k⌋k\lfloor n/k\rfloor 人继续游戏。

Wotan 想要尽快的结束这个游戏,因为他还要坐飞机去德国看 FC As- gard 俱乐部的足球赛。现在有 QQ 轮游戏,QQ 轮参与游戏的人数分别为n1,⋯ ,nQn_{1},\cdots ,n_{Q}, Wotan 想提前知道对于每一轮游戏 nj(1≤j≤Q)n_{j}(1\le j\le Q),至少需要报出几个数字才可以结束这轮游戏(即淘汰全部的njn_{j} 个小朋友)。

输入格式

从标准输入读入。

第一行包括两个整数mm 和 QQ。

第二行包含mm 个质数,表示 Wotan 可以使用的质数。接下来QQ 行每行 一个整数 nj(1≤j≤Q)n_{j}(1\le j\le Q),表示这一轮游戏的人数。

输出格式

向标准输出写出。

输出包括QQ 行, 对于一个 nj(1≤j≤Q)n_{j}(1\le j\le Q),如果 Wotan 可以结束游戏,那么输出报出的数字个数;否则输出字符串 oo(两个小写字母 ‘o’, 表示 +∞+\infty)。

样例输入1

2 2
2 3
5
6

样例输出1

3
oo

样例 1 解释

第一轮 5 个小朋友做游戏。

第一次 Wotan 可以报出 3,那么淘汰 2 名小朋友,剩下 3 名小朋友继续游戏;

第二次 Wotan 可以报出 2,那么淘汰 1 名小朋友,剩下 2 名小朋友继续游戏;

第三次 Wotan 可以报出 3,那么淘汰 2 名小朋友,所有小朋友均被淘汰, 第一轮游戏结束。

第二轮游戏,无论怎么报数都不可以淘汰所有的 6 个小朋友,所以无法结束游戏。

样例输入/输出 2

见 down/brunhildadown/brunhilda 下的brunhilda2.in/brunhilda2.ansbrunhilda2.in/brunhilda2.ans。

子任务

对于 20% 的数据,m,nj,Q≤10000m,n_{j},Q\le 10000 。

对于另外 20% 的数据,Q=1Q=1。

对于 100% 的数据,1≤m≤100000,1≤Q≤100000,2≤pi≤1\le m\le 100000,1\le Q\le 100000,2\le p_{i}\le 10000000,1≤nj≤1000000010000000,1\le n_{j}\le 10000000 。