[C++知识库]C. Hossam and Trainees #837 div2

Problem - C - Codeforces

判断n个数是否两两互质

分析：

这个好明显的一个板子题

板子名字叫做：判断n个数是否两两互质（n的范围1e5）

反过来理解就是题目意思所说：

是否有两个数有共同的因子

我想的是质因数分解，这里有个大坑。

在质因数分解的时候不用把分解了多少次给记录下来，因为我们本质要找的是两个数是否有公共的因子，那最后看mp[x]是否>1,如果记录次数，一个数可能分解出来是好几个2相乘，在遇到这种情况的时候。那就应该是只记录出现的数即可

然后每个数质因数分解一遍，你会发现超时

质因数分解的本质是每一个合数可以等于几个质数相乘

所以，我们把质数全部筛出来，然后把这些质数当作因子去质因数分解

嗯。接下来看代码，其他没什么好说的了

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include<iostream>
#include<map>
#include<set> 
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PAII;
const int N=2e6+10,M=5050,INF=1e18,mod=998244353,NN=10000010;
int prime[N],a[N];
bool st[NN];
int cnt;
map<int,int> mp;
void init()
{
	int n=N;
	for(int i=2;i<=n;i++)
	{
		if(!st[i]) prime[cnt++]=i;
		for(int j=0;prime[j]<=n/i;j++)
		{
			st[prime[j]*i]=true;
			if(i%prime[j]==0) break;
		}
	}
}
signed main(){
    //IOS;
    int T;
    //T=1;
    cin>>T;
    init();
    while(T--)
    {
    	mp.clear();
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	int f=0;
    	for(int i=1;i<=n;i++)
    	{
			int x=a[i];
			for(int j=0;prime[j]*prime[j]<=x;j++)
			{
				int xx=prime[j];
				if(x%xx==0)
				{
					while(x%xx==0) x/=xx;
					mp[xx]++;
					if(mp[xx]>1)
					{
						f=1;
						break;
					}
				}
			}
			if(x>1)
			{
				mp[x]++;
				if(mp[x]>1)
				{
					f=1;
					break;
				}
			}
			if(f) break;
		}
		if(f) cout<<"YES\n";
		else cout<<"NO\n"; 
	}
    return 0;
} 
/*



*/