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 \lt j \lt 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).$$

设 $a$、$b$、$c$ 为整数。我们定义函数 $f(a, b, c)$ 如下：

将数字 $a$、$b$、$c$ 按非降序排列，使得 $a \le b \le c$；然后返回 $\gcd(a, b)$，其中 $\gcd(a, b)$ 表示整数 $a$ 和 $b$ 的最大公约数（GCD）。

换言之，我们取三个数中较小的两个数的 $\gcd$，而忽略最大的那个数。

给定一个包含 $n$ 个元素的数组 $a$，请计算对所有满足 $1 \le i \lt j \lt k \le n$ 的三元组 $(i, j, k)$ 对应的 $f(a_i, a_j, a_k)$ 的总和。

更形式化地，计算

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 8 \cdot 10^4$）—— 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^5$）—— 数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $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$.

在第一个测试用例中，函数 $f$ 的取值如下：

• $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$。

所有三元组对应的函数值之和为 $1+1+1+2+2+2+3+3+3+6=24$。

在第二个测试用例中，共有 $56$ 种选择 $i$、$j$、$k$ 的方式。所有 $f(a_i,a_j,a_k)$ 的总和为 $203$。