C.Koxia and Number Theory
题意:给定 n 个数,问是否存在一个正整数 x ,使得对 \(\forall \ i,j \in [1,n]\) ,有 \(\gcd(a_i+x,a_j+x)=1\)
题解:
感觉这题挺难的,想了很多次也没想出来.
若两个数互质,一定不存在质数 \(p\) 使得 \(p\) 能整除这两个数.
如果存在一个质数使得 \(p\) 能整除至少两个数,也就说明这两个数一定不互质.
令 \(b_i = a_i+x\)
那么,能否判断对于 \(p\) ,是否总是整除至少两个 \(b_i\) ?(无论 \(x\) 的取值)
对于 \(a_i\%p = k\) ,显然当取 \(x = p-k\) 就整除了.
那么如果 \(a_i\%p\) 的模数 \([0,p-1]\) 都至少出现了两次,那么无论 \(x\) 怎么取值,一定都会使得某个 \(a_i+x%p\) 变成 \(0\) (出现至少两次,那么至少有两个这样的 \(i\) ),这样他们的最大公约数一定至少是 \(p\) ,这样直接输出 \(NO\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+10;
int primes[N];
int vis[N];
int idx = 0;
void getprime()
{
for(int i=2;i<N;i++)
{
if(!vis[i])
primes[idx++] = i;
for(int j=i+i;j<N;j+=i)
{
vis[j] = 1;
}
}
}
typedef pair<int,int> PII;;
void solve()
{
int n;
cin>>n;
vector<int> a(n);
map<int,bool> vis;
int flag = 1;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(vis[a[i]])
{
flag =0;
}
vis[a[i]]=1;
}
if(!flag)
{
cout<<"NO\n";
return ;
}
for(int u =0;u<idx&&primes[u]<=(n+1)/2;u++)
{
int p = primes[u];
// priority_queue< PII,vector<PII>,greater<PII> >q;
map<int,int> mp;
for(int i = 0;i<n;i++)
{
int num = a[i]%p;
mp[num]++;
// q.push({mp[num],num});
}
int flag = 0;
for(auto[x,y]:mp)
{
if(y<2)
{
flag =1;
}
}
if(!flag)
{
cout<<"NO\n";
return ;
}
}
cout<<"YES\n";
}
signed main()
{
getprime();
// for(int i=0;i<10;i++)
// {
// cout<<primes[i]<<'\n';
// }
int T;
cin>>T;
while(T--)
solve();
return 0;
}