AtCoder Beginner Contest 177, E : Coprime

問題文

　https://atcoder.jp/contests/abc177/tasks/abc177_e

問題概要

　$N$ 項からなる整数列 $\{ A_i \}$ が与えられる．
　任意の $i, j$ ($i < j$) について $\mathrm{ GCD }( A_i, A_j )$ のとき，$A$ は pairwise coprime であると言う．
　$A$ が pairwise coprime ではなく，$\mathrm{ GCD }( A_0, A_1, \dots, A_{ N - 1 } ) = 1$ のとき，$A$ は setwise coprime であると言う．
　$A$ が pairwise coprime でもなく setwise coprime でもないとき，$A$ は not coprime であると言う．
　$A$ が上記のいずれに該当するか判定せよ．

制約

• $2 \leq N, A_i \leq 10^6$

解法

　pairwise coprime の条件は，言い換えると「$2$ 要素に共通する素因数が存在しなければ coprime」となります．よって，$A$ の各要素を素因数分解して，共通する素因数があるかどうかを（std::map などで）調べることで判定できます．素因数分解が遅いと TLE の危機ですが，公式解説で「高速素因数分解」として参照されてる手法を使うと，複数の整数に対する素因数分解を高速に処理することができます．
　setwise coprime の条件は，単純に，$A$ の累積 $\mathrm{ GCD }$ が $1$ かどうかで判定できます．

コード

// N 項素因数分解
std::vector< vector< long long > > primeFactorization( std::vector< int > A );

bool pairwise_coprime( const VI &A )
{
	VVT< LL > pss = primeFactorization( A );

	map< int, int > factors;
	FOR( ps, pss )
	{
		reverse( ALL( ps ) );
		ps.erase( unique( ALL( ps ) ), end( ps ) );
		FOR( p, ps )
		{
			if ( ++factors[p] == 2 )
			{
				return false;
			}
		}
	}
	return true;
}

bool setwise_coprime( const VI &A )
{
	int g = A[0];
	for_each( ALL( A ), [&]( const int a ){ g = __gcd( g, a ); } );
	return g == 1;
}

int main()
{
	cin.tie( nullptr );
	ios::sync_with_stdio( false );
	cout << setprecision( 12 ) << fixed;

	IN( int, N );
	VI A( N );
	cin >> A;
	
	if ( pairwise_coprime( A ) )
	{
		cout << "pairwise coprime" << endl;
	}
	else if ( setwise_coprime( A ) )
	{
		cout << "setwise coprime" << endl;
	}
	else
	{
		cout << "not coprime" << endl;
	}

	return 0;
}