Shubham and GCD

4.8

12 votes
Medium
Problem

You are given an array of n integer numbers \(a_1\), \(a_2\), .. ,\(a_n\).

Define a function f(l,r) as the number of pairs \((i, j)\) such that \(l\le i\le j\le r\) and gcd(\(a_i\),\(a_j\)) != 1.

Output the sum of f(l,r) over all l, r such that \(1\le l\le r\le n\). If the sum is greater than \(10^{18}\), please output 1.

Input format

  • First line: n denoting the number of array elements
  • Second line: n space separated integers \(a_1\), \(a_2\), .. ,\(a_n\).

Output format

  • Output the required sum.

Constraints

\(1 \le n,a_i \le 100000\)

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

?