Powerful Inversions

Time Limit: 3000ms

Memory Limit: 256MB

M - Powerful Inversions

Submissions Submit

Ali told you that a powerful inversion is a pair of indices $(i, j)$ such that: 
$i < j$
$A_j$ is divisible by $A_i$
and decided to challenge you as follows:
 
You have an array $A$ of $n$ elements.
Let $F(L, R)$ be the number of powerful inversions in the subarray $[L, R]$.
Calculate the sum of $F(L, R)$ for all subarrays $[L, R]$ such that $1 \le L \le R \le n$.
 
Are you going to accept the challenge?

Input

The input consists of multiple test cases. The first line contains a single integer $T (1 \le T \le 10^4)$ --- the number of test cases.
The first line of each test case contains one integer $n (1 \le n \le 10^5)$ --- the number of elements in the array $a$.
The second line of each test case contains $n$ integers $a_1,a_2, \dots ,a_n (1 \le a_i \le  10^5)$ --- the elements of the array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, print only one integer, the sum of $F(L, R)$ for all the sub-arrays $[L, R]$ such that $(1 \le L \le R \le n)$

Notes

Explanation of the first test case:
$F(1, 1) = F(2, 2) = F(3, 3) = F(4, 4) = F(2, 3) = F(3, 4) = 0$.
$F(1, 2) = 1$ the inversions is $(1, 2)$.
$F(1, 3) = 2$ the inversions are $(1, 2)$ and $(1, 3)$.
$F(2, 4) = 1$ the inversion is $(2, 4)$.
$F(1, 4) = 4$ the inversions are $(1, 2), (1, 3), (1, 4), (2, 4)$.
The sum of $F(L, R)$ equals $8$.

Samples

Input	Output
2 4 1 2 3 4 5 1 5 2 4 3 Copy	8 16 Copy

Instead of iterating over all the subarrays, we will iterate over the powerful inversions.

For each powerful inversion, we will calculate its total contribution over the answer.

However, iterating over the powerful inversions will also give O(N * N) time complexity which will not pass.

What we will do is, for each (j), we will iterate over the value (X), such that (X) is divisible by (A[j]). So we are iterating over the value of (A[i] = X) instead of iterating over (i). And then we will add the total contribution for all pairs (i, j) such that the pair(i, j) is a powerful inversion.

We can iterate over all the candidates (X) in O(sqrt(A[j])) time complexity since it's sufficient to iterate over the divisors of (A[j]).

Now we have fixed a value (X) and an index (j), and we are interested in the total contribution.

For each (i) such that (i < j) and (A[i] = X), it will contribute into (number of ways to choose L) * (number of ways to choose R) subarrays, which equals (i) * (n - j + 1) subarrays.

So for a fixed value (X) and a fixed index (j), the total contribution can be written as:

(i1) * (n - j + 1)

+ (i2) * (n - j + 1)

+ (i3) * (n - j + 1)

+ ....

= (sum of i) * (n - j + 1).

So, if we stored the sum of indices (i) such that (A[i] = X) and (i < j), then we can calculate the contribution simply as sum[X] * (n - j + 1) in O(1).

Code sketch:

for (j = 1 to n) {
  for (all divisors X of A[j]) {
    add sum[X] * (n - j + 1) to the answer
  }
  increase sum[A[j]] by j
}

Bonus:
The problem can be solved in O(N * (N^(1/3))) using harmonic series.