提出 #16387453

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int gcd(int a,int b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}
set<int> fact(int z)
{
	set<int> ret;
	for(int j=2;j*j<=z;j++)
	{
		while(z%j==0)
			z/=j,ret.insert(j);
	}
	if(z!=1)
		ret.insert(z);
	return ret;
}
int main()
{
	int n;
	cin>>n;
	int a[n];
	bool pairwise=1;
	set<int> allfactors;
	int g=a[0];
	for(int p=0;p<n;p++)
	{
		cin>>a[p];
	}
	for(int p=0;p<n;p++)
	{
		if(p>0)
			g=__gcd(a[p],g);
	}
		
	for(int k=0;k<n;k++)
	{
		if(pairwise)
		{
			set<int> prime_factors=fact(a[k]);
			for(auto df:prime_factors)
			{
				if(allfactors.count(df)>0)
				{
					pairwise=0;
					break;
				}
				else
				{
					allfactors.insert(df);
				}
			}
		}
	}
	if(pairwise)
	{
		cout<<"pairwise coprime"<<endl;
	}
	else if(g==1)
	{
		cout<<"setwise coprime"<<endl;
	}
	else
	{
		cout<<"not coprime"<<endl;
	}
}

提出情報

ジャッジ結果