A16303 | $Small GCD$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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)](https://en.wikipedia.org/wiki/Greatest_common_divisor) 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.

输入 #1

2
5
2 3 6 12 17
8
6 12 8 10 15 12 18 16

输出 #1

24
203

C++ 编辑器

输入

输出