Small GCD
Contest: Codeforces Round 911 (Div. 2)
Difficulty rating: 2000
Tags: bitmasks, brute force, dp, math, number theory

Let $$$a$$$, $$$b$$$, and $$$c$$$ be integers. We define function $$$f(a, b, c)$$$ as follows:

Order the numbers $$$a$$$, $$$b$$$, $$$c$$$ in such a way that $$$a \le b \le c$$$. Then return $$$\gcd(a, b)$$$, where $$$\gcd(a, b)$$$ denotes the greatest common divisor (GCD) of integers $$$a$$$ and $$$b$$$.

So basically, we take the $$$\gcd$$$ of the $$$2$$$ smaller values and ignore the biggest one.

You are given an array $$$a$$$ of $$$n$$$ elements. Compute the sum of $$$f(a_i, a_j, a_k)$$$ for each $$$i$$$, $$$j$$$, $$$k$$$, such that $$$1 \le i < j < k \le n$$$.

More formally, compute $$$$$$\sum_{i = 1}^n \sum_{j = i+1}^n \sum_{k =j +1}^n f(a_i, a_j, a_k).$$$$$$

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 8 \cdot 10^4$$$) — length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$8 \cdot 10^4$$$.

Output format:
For each test case, output a single number — the sum from the problem statement.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the values of $$$f$$$ are as follows:

- $$$i=1$$$, $$$j=2$$$, $$$k=3$$$, $$$f(a_i,a_j,a_k)=f(2,3,6)=\gcd(2,3)=1$$$;
- $$$i=1$$$, $$$j=2$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(2,3,12)=\gcd(2,3)=1$$$;
- $$$i=1$$$, $$$j=2$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,3,17)=\gcd(2,3)=1$$$;
- $$$i=1$$$, $$$j=3$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(2,6,12)=\gcd(2,6)=2$$$;
- $$$i=1$$$, $$$j=3$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,6,17)=\gcd(2,6)=2$$$;
- $$$i=1$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,12,17)=\gcd(2,12)=2$$$;
- $$$i=2$$$, $$$j=3$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(3,6,12)=\gcd(3,6)=3$$$;
- $$$i=2$$$, $$$j=3$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(3,6,17)=\gcd(3,6)=3$$$;
- $$$i=2$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(3,12,17)=\gcd(3,12)=3$$$;
- $$$i=3$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(6,12,17)=\gcd(6,12)=6$$$.

In the second test case, there are $$$56$$$ ways to choose values of $$$i$$$, $$$j$$$, $$$k$$$. The sum over all $$$f(a_i,a_j,a_k)$$$ is $$$203$$$.

Example input:
2
5
2 3 6 12 17
8
6 12 8 10 15 12 18 16

Example output:
24
203

Editorial:
Let the maximum value in $$$a$$$ be $$$m$$$.
We will calculate array $$$x$$$, such that $$$x_i$$$ is the number of triples $$$i$$$, $$$j$$$, $$$k$$$ ($$$1 \le i < j < k \le n$$$) for which the value of $$$f(a_i, a_j, a_k)$$$ is equal to $$$i$$$. Then the answer is the sum of $$$i \cdot x_i$$$.
We calculate $$$x_i$$$ from $$$x_m$$$ to $$$x_1$$$. For some $$$i$$$, we can first calculate the number of triples that have value that is an integer multiple of $$$i$$$, and then from it subtract $$$x_{2i}, x_{3i}, x_{4i} \ldots$$$
The number of subractions is $$$\frac{M}{1} + \frac{M}{2} + \frac{M}{3} + \ldots + \frac{M}{M}$$$, which is around $$$M log M$$$, so the complexity of this step is $$$O(M log M)$$$.
Now the problem is how to count those triples.
As the order in which numbers are given does not matter, we can sort the array. Now for each number $$$d$$$ ($$$1 \le d \le M$$$) store indicies of all numbers that are divisble by $$$d$$$ in an array of vectors. Now we will for each number $$$d$$$ ($$$1 \le d \le M$$$) count the number of triples.
To find the number of triples that have gcd value that is an integer multiple of $$$d$$$, we can do the following. We go over the index of the number that will be value $$$b$$$ in the function. We can utilize the vectors we calculated in previous step for that. Say that current index is $$$i$$$. Then for value $$$c$$$ we can pick any number with index larger than $$$i$$$ as the array is sorted. For value $$$a$$$, we can pick any of the numbers divisible by $$$d$$$ with index less than $$$i$$$, the number of which we can get from the vector. By multiplying those $$$2$$$ numbers we get the number of triples that have $$$a_i$$$ as their middle value.
Let the maximal number of divisors a number up to $$$m$$$ can have be $$$D$$$. Then the previous step has complexity of $$$O(ND)$$$. The value of $$$D$$$ for given constraints is $$$128$$$, so the previous step is quite fast.
Total time complexity: $$$O(N log N + M log M + ND)$$$
Total memory complexity: $$$O(ND + M)$$$