Coprime

AtCoder

IDabc177_e

Time2000ms

Memory256MB

Difficulty—

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\leq i < j \leq N$. ${A_i}$ is said to be setwise coprime when ${A_i}$ is not pairwise coprime but $GCD(A_1,\ldots,A_N)=1$. Determine if ${A_i}$ is pairwise coprime, setwise coprime, or neither. Here, $GCD(\ldots)$ denotes greatest common divisor. ## Constraints * $2 \leq N \leq 10^6$ * $1 \leq A_i\leq 10^6$ ## Input Input is given from Standard Input in the following format: $N$ $A_1$ $\ldots$ $A_N$ [samples]

Samples

Input #1

3
3 4 5

Output #1

pairwise coprime

$GCD(3,4)=GCD(3,5)=GCD(4,5)=1$, so they are pairwise coprime.

Input #2

3
6 10 15

Output #2

setwise coprime

Since $GCD(6,10)=2$, they are not pairwise coprime. However, since $GCD(6,10,15)=1$, they are setwise coprime.

Input #3

3
6 10 16

Output #3

not coprime

$GCD(6,10,16)=2$, so they are neither pairwise coprime nor setwise coprime.

API Response (JSON)

{
  "problem": {
    "name": "Coprime",
    "description": {
      "content": "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\\leq i < j \\leq N$. ${A_i}$ is said to be setw",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc177_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have $N$ integers. The $i$\\-th number is $A_i$.\n${A_i}$ is said to be pairwise coprime when $GCD(A_i,A_j)=1$ holds for every pair $(i, j)$ such that $1\\leq i < j \\leq N$.\n${A_i}$ is said to be setw...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments