CodeForces 687B (Remainders Game)[中国剩余定理]

发表于 | 更新于 | | 阅读次数：

题目链接：http://codeforces.com/problemset/problem/687/B

这题是中国剩余定理解的性质。令M=lcm(c1,c2,…,cn)，则对x mod ci=ri用中国剩余定理求得的解在模M意义下是同余的，也即求得的解加上p*M可以得到通解。因而判断M%k==0是否成立，如果成立则x mod k的值是唯一的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
using namespace std;
const int maxn=1000009;
typedef long long LL;
int n,k;
LL gcd(LL a,LL b) {
    return b==0?a:gcd(b,a%b);
}
int main() {
    LL tmp=1;
    LL lcm=1;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) {
        scanf("%I64d",&tmp);
        LL d=gcd(lcm,tmp);
        lcm=lcm*tmp/d;
        lcm%=k;
    }
    printf(lcm==0?"Yes":"No");
}