Coprime Pairs

Difficulty: 2100 6000 ms 128 MB

number-theory mobius

Count the index pairs i < j with gcd(a_i, a_j) = 1.

Input: the first line has N; the second line has N positive integers.

Output: the number of coprime pairs.

Constraints:

• 2 ≤ N ≤ 10⁵
• 1 ≤ a_i ≤ 10⁵

Sample Tests

3
2 3 4

2

2
6 6

0

Read the Editorial