Codeforces Round 911 (Div. 2)

D. Small GCD

https://codeforces.com/contest/1900/problem/D

2 seconds / 256 megabytes

standard input / standard output

## Problem

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

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

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

## Example

Input

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

Output

24
203

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

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

## 题解

$$\sum_{1\leq i<j< n}\gcd(a_i,a_j)\times(n-j-1)$$

$$\sum_{i=1}^{N}i\cdot c_i$$

$$\sum_{i=1}^{N}i\cdot c_i$$

## 代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

constexpr int MAXN = 1e5 + 10;

vector<int> dv[MAXN];

void init()
{
for (int i = 1; i < MAXN; i++)
for (int j = i; j < MAXN; j += i)
dv[j].push_back(i);
}

void solve()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a.begin(), a.end());
int mx = a.back();
vector<int> num(mx + 10), cnt(mx + 10);
for (int i = 0; i < n; i++)
{
for (auto &d : dv[a[i]])
{
cnt[d] += (n - i - 1) * num[d];
num[d]++;
}
}
for (int i = mx; i >= 1; i--)
for (int j = i * 2; j <= mx; j += i)
cnt[i] -= cnt[j];
int ans = 0;
for (int i = 1; i <= mx; i++)
ans += cnt[i] * i;
cout << ans << endl;
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}