Good Bye 2022: 2023 is NEAR C Koxia and Number Theory

我会带着你远行 2024-03-30 13:31 72阅读 0赞

[Problem - C - Codeforces][]

题意：

给定一个数列a，问你是否存在一个数 x 使得所有数加上x之后两两互质

思路：

一、

我们知道一个结论，一些数两两之间互质，就说明所有数之间的质因子都不重合

如果要我们去判断一堆数之间是不是两两互质，就去给每个数都去分解质因数，然后把质因数放进map里，看存不存在某个质因数使得 mp\[p\]>=2，如果存在就说明没有两两互质

所以问题就转化为：是否存在 x ，使得所有数加上 x 之后，彼此之间质因数没有重合

二、

我们需要明白这样一件事情，对于一个数 a ，我们把它分解质因数为

![c5c4168ceca04940b51f6e656cee320c.png][]

然后我们把a加上x，会发生什么

对于a的一个质因子pk：（下图中一个小格子代表pk长度，因为能整除pk，所以可以画成这样，黄色部分就代表 a）

![345b5e17889149179542aa5b9f109866.png][]

加上 x 之后：（其中新加的黄色部分就是 x）

![a66333fc83624e8ab3704b3e99a72aef.png][]

这样的话，a就不再有质因子pk，因为加上 x 之后模pk不再为0

三、

知道了一的结论和二的感性理解后，我们再去看题目：

我们是否能构造出 x ，使得所有数加 x 之后没有重合的质因子

首先，如果数列中存在一样的数就是NO，因为这样一定不存在 x 使得 gcd(ai+x,ai+x)=1

这个gcd一定等于 ai+x 嘛

我们去枚举质因子

对于一个质因子pi，如果在加x之前的数列中，存在两个数 ai , aj，使得 ai%pi==aj%pi

比如

ai ：

![f1c948b4780d485e98e48c6a915ac6db.png][]

aj：

![a66333fc83624e8ab3704b3e99a72aef.png][]

那么我们取 x = pi - ai%pi ，这样加了 x 之后，ai 和 aj 会有同一个质因子 p

（下图中绿色部分就是 x ，因为加了 x 之后模 pi 都为 0，因此 ai+x 和 aj+x 含有同一个质因子 pi）

ai+x：

![ba6cd7e885dd408e97fc4bcc3901e95a.png][]

aj+x：

![b8699f0d1a754d448c7cf029f9c0f0a4.png][]

那我们要避免 ai+x 和 aj+x 有同一个质因子的情况发生，就不能取 x = pi - ai%pi

这样只是在数列 a 中拿出了两个数 ai 和 aj 而已，对于数列 a 中的数 ai，x 都不能等于pi - ai%pi

而 pi - ai%pi 的取值在 \[0,p-1\]之间，也就是说它只有 p 种取值，因此如果说这 p 种取值都被取到了且每种取值都出现了两次及以上，就说明 x 就没得选了，因为这样的话无论 x 取什么值，总存在两个数 ai 和 aj ，使得 ai+x 和 aj+x 有相同质因子 pi

所以做法就是：我们去枚举质因子 pk ，对于每一个质因子 pk ，都去统计 ai % pk 的出现次数，如果所有的 ai% pk 的出现次数全都 >=2，x 就没得选了，否则就取 ai % pk 的出现次数<=1 的 pk ，然后令 x= pk - ai%pk 就行

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e2+10;
    int n;
    int a[mxn];
    void solve(){
    	cin>>n;
    	map<int,int> mp2;
    	for(int i=1;i<=n;i++) cin>>a[i],mp2[a[i]]++;
    	for(int i=1;i<=n;i++){
    		if(mp2[a[i]]>1){
    			cout<<"NO"<<'\n';
    			return;
    		}
    	}
    	for(int p=2;p<=n;p++){
    		map<int,int> mp;
    		for(int i=1;i<=n;i++) mp[a[i]%p]++;
    		int cnt=0;
    		for(auto it:mp){
    			if(it.second>=2) cnt++;
    		}
    		if(cnt==p){
    			cout<<"NO"<<'\n';
    			return;
    		}
    	}
    	cout<<"YES"<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1770/problem/C
[c5c4168ceca04940b51f6e656cee320c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f699259ec5004fd1b0e244c9f14f06d2.png
[345b5e17889149179542aa5b9f109866.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3ff58e3e70bd410d83229047412c07b1.png
[a66333fc83624e8ab3704b3e99a72aef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/dd8d166b85ed4c38ac158c669844f6bb.png
[f1c948b4780d485e98e48c6a915ac6db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/756f61c5e5724e1ba4129af9e04c5faf.png
[ba6cd7e885dd408e97fc4bcc3901e95a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d164c89c28fa4fd499e490a368a147ab.png
[b8699f0d1a754d448c7cf029f9c0f0a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/311a1a3ecd2241a790438c08acd18fb9.png