CF1900D.Small GCD

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). $$$$

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$ .

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

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$ .

The sum over all triples is $1+1+1+2+2+2+3+3+3+6=24$ .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$ .