Coprime

题目描述

我们有 $N$ 个整数。第 $i$ 个数是 $A_i$。 当对任意满足 1\leq i < j \leq N 的每一对 $(i, j)$ 都有 $GCD(A_i,A_j)=1$ 时，称 $\{A_i\}$ 为两两互素（pairwise coprime）。 当 $\{A_i\}$ 不是两两互素但 $GCD(A_1,\ldots,A_N)=1$ 时，称 $\{A_i\}$ 为集合互素（setwise coprime）。 判断 $\{A_i\}$ 是两两互素、集合互素，还是都不是。 这里，$GCD(\ldots)$ 表示最大公约数。

输入格式

输入按如下格式从标准输入给出： $N$ $A_1$ $\ldots$ $A_N$

输出格式

如果 $\{A_i\}$ 是两两互素，输出 $pairwise coprime$；如果 $\{A_i\}$ 是集合互素，输出 $setwise coprime$；如果两者都不是，输出 $not coprime$。

3
3 4 5

pairwise coprime

3
6 10 15

setwise coprime

3
6 10 16

not coprime

提示

$2 \leq N \leq 10^6$ $1 \leq A_i\leq 10^6$$GCD(3,4)=GCD(3,5)=GCD(4,5)=1$，所以它们是两两互素。
由于 $GCD(6,10)=2$，它们不是两两互素。然而，因为 $GCD(6,10,15)=1$，它们是集合互素。
$GCD(6,10,16)=2$，因此它们既不是两两互素也不是集合互素。

标签: AtCoder|abc177E

来源

AtCoder|abc177E