Shubham and GCD

4.8

12 votes
Medium
Problem

You are given an array of n integer numbers a1, a2, .. ,an.

Define a function f(l,r) as the number of pairs (i,j) such that lijr and gcd(ai,aj) != 1.

Output the sum of f(l,r) over all l, r such that 1lrn. If the sum is greater than 1018, please output 1.

Input format

  • First line: n denoting the number of array elements
  • Second line: n space separated integers a1, a2, .. ,an.

Output format

  • Output the required sum.

Constraints

1n,ai100000

Sample Input
3
2 4 6
Sample Output
15
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

f(1,1) = 1
f(1,2) = 3
f(1,3) = 6
f(2,2) = 1
f(2,3) = 3
f(3,3) = 1
sum = 1 + 3 + 6 + 1 + 3 + 1 = 15

Editor Image

?