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;
}