#P6962. [2018年5月雅礼集训]⽣⽇聚会
[2018年5月雅礼集训]⽣⽇聚会
生日聚会
题目背景
Brunhilda 就快要 7 岁了。今年她决定在拉脱维亚过生日。拉脱维亚位于东欧波罗的海沿岸,有欧洲北部巴黎之称。首都里加建筑美轮美奂,而远离首都的小镇更是自然风光无限好,休闲时间她也去野外、海边、山地露营游玩。现在,她正在筹备她的 7 岁生日 party。
问题描述
Brunhilda 发明了如下的游戏:所有的小朋友围成一圈跑动起来,直到听到数字 k。接着,所有的小朋友都互相抱紧尽量使自己在一个人数正好为 k 的小组中。只要剩下的小朋友个数至少有 k 个,那么就一定会形成一个新的 k 个小朋友的小组。最后,会留下少于 k 个小朋友,那么这些小朋友就会被淘汰。出于 Brunhilda 对骑士盔甲的喜爱,最后所有的小朋友都会被淘汰。一 旦小朋友全部被淘汰了,这轮游戏也就结束了。
Brunhilda 叫她的爸爸 Wotan 帮忙报数字。Wotan 并没有表现出对这个游戏多大的喜爱,于是在一开始就报出了 。Brunhilda 觉得在 party 上出现这样的状况实在是太尴尬了,于是她给了她的爸爸一些质数,要他每次报数时从中间选择一个数字。爸爸可以使用同一个数字多次。也就是说,当前有 个小朋友时,报数 后淘汰 人,留下 人继续游戏。
Wotan 想要尽快的结束这个游戏,因为他还要坐飞机去德国看 FC As- gard 俱乐部的足球赛。现在有 轮游戏, 轮参与游戏的人数分别为, Wotan 想提前知道对于每一轮游戏 ,至少需要报出几个数字才可以结束这轮游戏(即淘汰全部的 个小朋友)。
输入格式
从标准输入读入。
第一行包括两个整数 和 。
第二行包含 个质数,表示 Wotan 可以使用的质数。接下来 行每行 一个整数 ,表示这一轮游戏的人数。
输出格式
向标准输出写出。
输出包括 行, 对于一个 ,如果 Wotan 可以结束游戏,那么输出报出的数字个数;否则输出字符串 oo(两个小写字母 ‘o’, 表示 )。
样例输入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
见 下的。
子任务
对于 20% 的数据, 。
对于另外 20% 的数据,。
对于 100% 的数据, 。