《CF687B Remainders Game》
题目描述
今天 Pari 和 Arya 正在玩一个叫做“余数”的游戏。
Pari 选择两个正整数 x 和 k，并将 k 告诉 Arya，但不告知 x。Arya 需要找出 xmodk 的值。有 n 个古老的数字 c1,c2,...,cn，如果 Arya 想知道 xmodci 的值，Pari 必须如实告知。
给定 k 和这些古老的数字，请判断 Arya 是否可以采取一种独立于 x 的必胜策略。形式化地说，无论 x 取何正整数，Arya 是否总能根据所给信息确定 xmodk 的值？
注意，xmody 表示 x 除以 y 的余数。
输入格式
输入的第一行包含两个整数 n 和 k（1≤n, k≤1000000）——古老整数的数量与 Pari 选择的 k。
第二行包含 n 个整数 c1,c2,...,cn（1≤ci≤1000000）。
输出格式
如果 Arya 存在独立于 x 的必胜策略，输出 “Yes”（不含引号）；否则输出 “No”。
显示翻译
题意翻译
输入输出样例
输入 #1复制
4 5 2 3 5 12
输出 #1复制
Yes
输入 #2复制
2 7 2 3
输出 #2复制
No
说明/提示
在第一个样例中，Arya 可以确定 xmod5，因为 5 就是其中一个古老数字。
在第二个样例中，Arya 无法确定 xmod7 的值。例如 1 和 7 对 2 和 3 取余时余数相同，但对 7 取余时余数不同。
由 ChatGPT 5 翻译
代码实现：
#include <bits/stdc++.h> #define int long long #define LL long long using namespace std; const int N = 1e6 + 10; int a[N], n, m; LL res = 0; inline int rd() { int x = 0, f = 1; char c = getchar(); while (c<'0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } void wt(string s) { // 替换范围for循环为传统下标遍历 for (int i = 0; i < s.size(); i++) { putchar(s[i]); } } int gcd(int a, int b) { return a % b == 0 ? b : gcd(b, a % b); } int lcm(int a, int b) { return a * b / gcd(a, b); } signed main(){ int T; int x = 1; n = rd(); m = rd(); for (int i = 1; i <= n; i++) { a[i] = rd(); x = lcm(x, a[i]) % m; } if (x % m == 0) { wt("Yes"); } else wt("No"); putchar('\n'); return 0; }