← 返回题目列表

AtCoder · abc177_e

E. 共质

中文机器翻译题面 查看原题

分数: 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,所以它们既不是成对互质也不是集合互质。