GCD 与火锅底料
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
火锅店有 包底料,第 包底料的辣度为 。
有 位同学来点锅底。第 位同学给出一个整数 ,他只愿意选择辣度 与 互质的底料,也就是:。
请你对每位同学回答:有多少包底料符合他的要求?
同学们的问题很多,老板不想每次都翻完整个仓库。毕竟底料会累,老板也会。
Format
Input
第一行两个整数 。
第二行 个整数 。
接下来 行,每行一个整数 ,表示一次询问。
Output
对于每次询问,输出一行一个整数,表示满足 的 数量。
Samples
6 4
2 3 4 6 9 25
6
5
10
7
1
5
2
6
Note
样例说明:
对于 ,只有 与 互质,答案为 。
对于 ,除 外的五个数都与 互质,答案为 。
对于 , 和 与 互质,答案为 。
对于 ,所有数都与 互质,答案为 。
2026江南程序设计竞赛联盟暑期多校训练-摸底赛(重现)
- Status
- Done
- Rule
- XCPC
- Problem
- 11
- Start at
- 2026-10-14 13:45
- End at
- 2026-10-14 17:45
- Duration
- 4 hour(s)
- Host
- Partic.
- 2