提出 #16386994

ソースコード 拡げる

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll a,ll b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}
set<ll> fact(ll z)
{
	set<ll> ret;
	for(ll 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()
{
	ll n;
	cin>>n;
	ll a[n];
	bool pairwise=1;
	set<ll> allfactors;
	ll g=a[0];
	for(ll p=0;p<n;p++)
	{
		cin>>a[p];
	}
	for(ll p=0;p<n;p++)
	{
		if(p>0)
			g=gcd(a[p],g);
	}
		
	for(ll k=0;k<n;k++)
	{
		if(pairwise)
		{
			set<ll> 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;
	}
}

提出情報

提出日時
問題 E - Coprime
ユーザ BhawnaGupta
言語 C++ (GCC 9.2.1)
得点 0
コード長 932 Byte
結果 WA
実行時間 463 ms
メモリ 11412 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 500
結果
AC × 2
WA × 1
AC × 25
WA × 1
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, max_01.txt, max_02.txt, max_03.txt, max_04.txt, max_05.txt, max_11.txt, max_12.txt, max_13.txt, max_14.txt, max_15.txt, max_16.txt, max_17.txt, max_18.txt, pair_01.txt, pair_02.txt, pair_03.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, sample_01.txt, sample_02.txt, sample_03.txt
ケース名 結果 実行時間 メモリ
hand_01.txt AC 2 ms 3520 KiB
max_01.txt AC 123 ms 11220 KiB
max_02.txt AC 217 ms 11412 KiB
max_03.txt AC 235 ms 11196 KiB
max_04.txt AC 220 ms 11328 KiB
max_05.txt AC 451 ms 7760 KiB
max_11.txt AC 49 ms 4748 KiB
max_12.txt AC 122 ms 11336 KiB
max_13.txt AC 350 ms 6808 KiB
max_14.txt AC 458 ms 7760 KiB
max_15.txt AC 460 ms 7860 KiB
max_16.txt AC 460 ms 7784 KiB
max_17.txt AC 463 ms 7804 KiB
max_18.txt AC 456 ms 7732 KiB
pair_01.txt AC 460 ms 7824 KiB
pair_02.txt AC 451 ms 7668 KiB
pair_03.txt AC 460 ms 7804 KiB
random_01.txt AC 26 ms 3860 KiB
random_02.txt AC 20 ms 3848 KiB
random_03.txt AC 24 ms 3876 KiB
random_04.txt AC 24 ms 3972 KiB
random_05.txt AC 23 ms 4072 KiB
random_06.txt AC 30 ms 3916 KiB
sample_01.txt AC 2 ms 3380 KiB
sample_02.txt WA 2 ms 3568 KiB
sample_03.txt AC 2 ms 3452 KiB