E - 互质

分数 : $500$ 分

题目描述

我们有 $N$ 个整数。第 $i$ 个数为 $A_i$。

当对于每一对满足 $1\leq i < j \leq N$ 的 $(i, j)$，都有 $GCD(A_i,A_j)=1$ 时，$\{A_i\}$ 被称为两两互质。

当 $\{A_i\}$ 不是两两互质但是 $GCD(A_1,\ldots,A_N)=1$ 时，$\{A_i\}$ 被称为集合互质。

判断 $\{A_i\}$ 是两两互质、集合互质还是都不是。

这里，$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；如果 $\{A_i\}$ 是集合互质，输出 setwise coprime；如果不是，输出 not coprime。

3
3 4 5

pairwise coprime

$GCD(3,4)=GCD(3,5)=GCD(4,5)=1$，所以它们两两互质。

3
6 10 15

setwise coprime

因为 $GCD(6,10)=2$，它们不是两两互质。然而，因为 $GCD(6,10,15)=1$，它们是集合互质。

3
6 10 16

not coprime

$GCD(6,10,16)=2$，所以它们既不是两两互质也不是集合互质。