/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個の整数があります。i 番目の数は A_i です。
「全ての 1\leq i < j \leq N について、GCD(A_i,A_j)=1」が成り立つとき、\{A_i\} は pairwise coprime であるといいます。
\{A_i\} が pairwise coprime ではなく、かつ、GCD(A_1,\ldots,A_N)=1 であるとき、\{A_i\} は setwise coprime であるといいます。
\{A_i\} が pairwise coprime、setwise coprime、そのどちらでもない、のいずれであるか判定してください。
ただし GCD(\ldots) は最大公約数を表します。
制約
- 2 \leq N \leq 10^6
- 1 \leq A_i\leq 10^6
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N
出力
\{A_i\} が pairwise coprime ならば pairwise coprime、setwise coprime ならば setwise coprime、そのどちらでもなければ not coprime と出力せよ。
入力例 1
3 3 4 5
出力例 1
pairwise coprime
GCD(3,4)=GCD(3,5)=GCD(4,5)=1 なので pairwise coprime です。
入力例 2
3 6 10 15
出力例 2
setwise coprime
GCD(6,10)=2 なので pairwise coprime ではありませんが、GCD(6,10,15)=1 なので setwise coprime です。
入力例 3
3 6 10 16
出力例 3
not coprime
GCD(6,10,16)=2 なので、pairwise coprime でも setwise coprime でもありません。
Score : 500 points
Problem Statement
We have N integers. The i-th number is A_i.
\{A_i\} is said to be pairwise coprime when GCD(A_i,A_j)=1 holds for every pair (i, j) such that 1\leq i < j \leq N.
\{A_i\} is said to be setwise coprime when \{A_i\} is not pairwise coprime but GCD(A_1,\ldots,A_N)=1.
Determine if \{A_i\} is pairwise coprime, setwise coprime, or neither.
Here, GCD(\ldots) denotes greatest common divisor.
Constraints
- 2 \leq N \leq 10^6
- 1 \leq A_i\leq 10^6
Input
Input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
If \{A_i\} is pairwise coprime, print pairwise coprime; if \{A_i\} is setwise coprime, print setwise coprime; if neither, print not coprime.
Sample Input 1
3 3 4 5
Sample Output 1
pairwise coprime
GCD(3,4)=GCD(3,5)=GCD(4,5)=1, so they are pairwise coprime.
Sample Input 2
3 6 10 15
Sample Output 2
setwise coprime
Since GCD(6,10)=2, they are not pairwise coprime. However, since GCD(6,10,15)=1, they are setwise coprime.
Sample Input 3
3 6 10 16
Sample Output 3
not coprime
GCD(6,10,16)=2, so they are neither pairwise coprime nor setwise coprime.