AT_abc177_e [ABC177E] Coprime

题目描述

有 $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)$ 表示最大公约数。

输入格式

输入从标准输入中给出，格式如下：

$N$ $A_1$ $\ldots$ $A_N$

输出格式

如果 $\{A_i\}$ 是 pairwise coprime，则输出 pairwise coprime；如果是 setwise coprime，则输出 setwise coprime；否则输出 not coprime。

输入输出样例 #1

输入 #1

3
3 4 5

输出 #1

pairwise coprime

输入输出样例 #2

输入 #2

3
6 10 15

输出 #2

setwise coprime

输入输出样例 #3

输入 #3

3
6 10 16

输出 #3

not coprime

说明/提示

限制条件

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

样例解释 1

因为 $GCD(3,4) = GCD(3,5) = GCD(4,5) = 1$，所以是 pairwise coprime。

样例解释 2

因为 $GCD(6,10) = 2$，所以不是 pairwise coprime，但 $GCD(6,10,15) = 1$，所以是 setwise coprime。

样例解释 3

因为 $GCD(6,10,16) = 2$，所以既不是 pairwise coprime，也不是 setwise coprime。

由 ChatGPT 4.1 翻译