CF687B Remainders Game

是个汉子 · 2020-08-26 22:27:38 · 题解

题目大意

现选定一个 k 与 x， x 未知，给出 n 个数 c ,可否根据 x 与 c 之间模数得出 x 模 k

解题思路

据 ex 中国剩余定理，可以知道

我们总可以将两个同余式子

转化为一个式子

其中 k_1 为方程 k_1m_1-k_2m_2=a_2-a_1 ​的一个解

而易证当 d|m 时，且 x\mod m 确定时 x\mod d 也就确定了

由此，我们只需求出所有的数之间的最小公倍数，观察k是否为这些数中任一的因数即可

代码

#include<iostream>
#include<cstdio>
#define ll long long

using namespace std;
ll n,k,tmp,x;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

ll gcd(ll m,ll n){
    return n==0?m:gcd(n,m%n);
}

ll lcm(int x,int y){
    return x/gcd(x,y)*y;
}

int main(){
    n=read();k=read();
    tmp=1;
    for(int i=1;i<=n;i++){
        x=read();
        if(!tmp) continue;
        tmp=lcm(tmp,x);
        tmp%=k;
    }
    printf("%s\n",!tmp?"Yes":"No");
    return 0;
}