分数: 500 点
问题陈述
我们有 N 整数。的 i第一个数字是 A_i.
\{A_i\} 被称为成对互质,当 GCD(A_i,A_j)=1 适用于每对 (i, j) 这样 1\leq i < j \leq N.
\{A_i\} 被称为集合互质,当 \{A_i\} 不是成对互质,而是 GCD(A_1,\ldots,A_N)=1.
确定是否 通过执行该操作零次或多次可以使 \{A_i\} 是成对互质、集合互质或两者都不是。
在这里, GCD(\ldots) 表示最大公约数。
约束
- 2 \leq N \leq 10^6
- 1 \leq A_i\leq 10^6
输入
输入由标准输入按以下格式给出:
N A_1 \ldots A_N
输出
If \{A_i\} 是两两互质,打印 pairwise coprime;如果 \{A_i\} 是 setwise 互质,打印 setwise coprime;如果两者都不是,则打印 not coprime.
示例输入 1
3 3 4 5
示例输出 1
pairwise coprime
GCD(3,4)=GCD(3,5)=GCD(4,5)=1,所以它们是成对互质的。
示例输入 2
3 6 10 15
示例输出 2
setwise coprime
自从 GCD(6,10)=2,它们不是成对互质。然而,自从 GCD(6,10,15)=1,它们是集合互质的。
示例输入 3
3 6 10 16
示例输出 3
not coprime
GCD(6,10,16)=2,所以它们既不是成对互质也不是集合互质。