Codeforces Round 911 (Div. 2) |
---|
Finished |
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.
252 3 6 12 1786 12 8 10 15 12 18 16
24 203
In the first test case, the values of $$$f$$$ are as follows:
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$$$.
Name |
---|