codeforces 687B - Remainders Game 数学相关（互质中国剩余定理）

题意：给你x%ci=bi（x未知）,是否能确定x%k的值（k已知）

——数学相关知识：

首先：我们知道一些事情，对于k,假设有ci%k==0,那么一定能确定x%k的值，比如k=5和ci=20，知道x%20=y，那么ans=x%k=y%5;

介绍（互质版）中国剩余定理，假设已知m1,m2,mn，两两互质,且又知道x%m1,x%m2..x%mn分别等于多少

设M=m1*m2*m3..mn,那么x在模M的剩余系下只有唯一解（也就是知道了上面的模线性方程组，就可以求出x%M等于多少）

——此题解法

针对这个题呢，我们要确定x%k，只要保证知道上述的互质的模线性方程组就好

怎么样得到模线性方程组呢，直接把k唯一分解就好

即：k=p1^k1*p2^k2...*pr^kn，如果任意i，都有pi^ki的倍数出现在集合中(这一点如果不懂可以看上面，如果知道一个数倍数的取模，那么它肯定也知道)，那么k就能被猜出来。

分析：只要保证k能整除ci的最小公倍数即可，由于太大，所以通过暴力分解因子的办法来判断

#include <cstdio>

#include <iostream>

#include <ctime>

#include <vector>

#include <cmath>

#include <map>

#include <set>

#include <stack>

#include <queue>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long LL;

const int N=1e5+;

const int INF=0x3f3f3f3f;

const int mod=1e9+;

bool cov[];

int n,k,cnt,fac[];

int main(){

    scanf("%d%d",&n,&k);

    for(int i=;i<=k;++i){

      if(k%i)continue;

       int cur=;

       while(k%i==)cur*=i,k/=i;

       fac[++cnt]=cur;

    }

    for(int i=;i<n;++i){

      int x;scanf("%d",&x);

      for(int j=;j<=cnt;++j)

        if(x%fac[j]==)cov[j]=true;

    }

    bool flag=;

    for(int i=;i<=cnt;++i)

      if(!cov[i])flag=;

    if(flag)printf("Yes\n");

    else printf("No\n");

    return ;

}