Sum of Pairwise GCDs

Difficulty: 2100 6000 ms 128 MB

number-theory

Print ∑_i<j gcd(a_i, a_j).

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

Output: the sum of gcd over all pairs.

Constraints:

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

Sample Tests

3
2 4 6

6

2
5 5

5

Read the Editorial