5623: ABC177——E - Coprime
[Creator : ]
Description
We have $N$ integers. The $i$-th number is $A_i$.
$\{A_i\}$ is said to be pairwise coprime when ${GCD}(A_i,\ A_j)=1$ holds for every pair $(i,\ j)$ such that $1≤i<j≤N$.
$\{A_i\}$ is said to be setwise coprime when $\{A_i\}$ is not pairwise coprime but ${GCD}(A_1,\ \dot,\ A_N)=1$.
Determine if $\{A_i\}$ is pairwise coprime, setwise coprime, or neither.
Here, ${GCD}(\dot)$ denotes greatest common divisor.
$\{A_i\}$ is said to be pairwise coprime when ${GCD}(A_i,\ A_j)=1$ holds for every pair $(i,\ j)$ such that $1≤i<j≤N$.
$\{A_i\}$ is said to be setwise coprime when $\{A_i\}$ is not pairwise coprime but ${GCD}(A_1,\ \dot,\ A_N)=1$.
Determine if $\{A_i\}$ is pairwise coprime, setwise coprime, or neither.
Here, ${GCD}(\dot)$ denotes greatest common divisor.
Input
Input is given from Standard Input in the following format:
$N$
$A_1\ A_2\ \dot A_N$
$N$
$A_1\ A_2\ \dot A_N$
Output
If $\{A_i\}$ is pairwise coprime, print ${pairwise coprime}$; if $\{A_i\}$ is setwise coprime, print ${setwise coprime}$; if neither, print ${not coprime}$.
Constraints
$2 \leq N \leq 10^6$
$1 \leq A_i \leq 10^6$
$1 \leq A_i \leq 10^6$
Sample 1 Input
3
3 4 5
Sample 1 Output
pairwise coprime
${GCD}(3,\ 4)={GCD}(3,\ 5)={GCD}(4,\ 5)=1$, so they are pairwise coprime.
Sample 2 Input
3
6 10 15
Sample 2 Output
setwise coprime
Since ${GCD}(6,\ 10)=2$, they are not pairwise coprime. However, since ${GCD}(6,\ 10,\ 15)=1$, they are setwise coprime.
Sample 3 Input
3
6 10 16
Sample 3 Output
not coprime
${GCD}(6,\ 10,\ 16)=2$, so they are neither pairwise coprime nor setwise coprime.
HINT
题目来源：AtCoder ABC177 E 题。