C. Koxia and Number Theory

原题链接Problem - C - Codeforces

题意：a数组有n个数，看是否能找出一个x，让其中的任意两个数分别+x之后的两个数的gcd都是1

思路：

如果有相同的数那么肯定是no

对于一组数中，如果每两个数的gcd都是1的话，说明这n个数的质因子没有重合的

那么就转换为我们要找一个x，使得任何两个ai+x和aj+x的质因子没有重合的情况

那么我们可以先排除x不能取的值

设一个质因数p，gcd（ai+x，aj+x）=p

因为ai和aj是加上同一个数x模上p之后是0，所以ai和aj分别模p的值相等

这种情况下的x=p-ai%p （ai%p的值差多少到p）

然而这个x是不能选的，所以我们就排除x=p-ai%p

因为x=p-ai%p，所以x的范围是0~p-1

那么如果这0~p-1内的所有数都不能取的话，说明无论x取什么都能让至少两个数的gcd是p

不能取的情况是a数组里所有的数%p之后的值y的个数>=2

那么其实我们列举每个质因数p，然后判断0~p-1范围内的数被a数组%p之后的数的个数是不是都>=2

如果都>=2说明一定是no

如果不是上面的情况，即对于所有p，都有一个a数组%p的值的个数<2的数，那么x就一定能找到吗？

这时就用到了中国剩余定理：

如果对于一个x, x%p1=y1 x%p2=y2 x%p3=y3...x%pm=ym

p1,p2,p3..pm两两互质，那么x就肯定能算出来

所以我们对于每个质因数p，都能找到一个%p的个数是1的数，这就相当于找到了一个形如x%pi=yi的等式，那么最后一定有解

但是我们注意到ai的范围是1e18，那我们对每个ai找质因数肯定会超时

这个时候我们想，如果n个数能把0~p-1都占满且每个位置放两个数，那么p最大就是n/2

p如果>p/2，肯定有位置放的数<2，那么就能找到x

所以，其实就是对所有的2~n/2的质数p，看看每个ai%p的值是否在0~p-1的范围上全都>=2，如果是的话就是no，不是就是yes

还能再简化一步：不用求0~n/2中的质数，合数是由质数相乘得到的，如果所有质数满足这个条件那么合数也满足，所以直接求2~n/2内的数能不能满足条件就行了

#include<bits/stdc++.h>
using namespace std;
#define int long long
#include<map>
const int N=200+10;
int n,m;
int a[N];
void sove(){
    cin>>n;
    map<int,int> mp1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp1[a[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(mp1[a[i]]>=2){
            cout<<"NO"<<endl;
            return ;
        }
    }
    for(int p=2;p<=n/2;p++){
        map<int,int> mp2;
        int cnt=0;
        for(int i=1;i<=n;i++){
            int op=a[i]%p;
            mp2[op]++;
        }
        for(auto x:mp2){
            if(x.second>=2)cnt++;
        }
        if(cnt==p){
            cout<<"NO"<<endl;
            return ;
        }
    }
    cout<<"YES"<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(),cout.tie();
    int t;
    cin>>t;
    while(t--){
        sove();
    }
    return 0;
}