Codeforces 687B Remainders Game

链接

传送门

题意

给出整数$n,k(1 \leq n, k \leq 1000000)$,接着给出$n$个整数$c_i$,在已知$x \mod {c_i}$的前提下,能否唯一的确定$x \mod k$。

思路

将$k$进行分解,对于每个质数,如果都存在$c_i$中的质数的幂比$k$中的大,则能唯一的确定$x \mod k$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b) {
return b ? gcd(b, a % b) : a;
}
LL lcm(LL a, LL b) {
return a / gcd(a, b) * b;
}
int main() {
int n, k, c;
LL cur = 1;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; ++i) {
scanf("%d", &c);
cur = lcm(cur, gcd(c, k));
}
puts(cur == k ? "Yes" : "No");
return 0;
}

支付宝扫码领红包