Small GCD (Codeforces 1900D)
Tags: Math, bitmasks

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.

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

Sample Inputs:
2
5
2 3 6 12 17
8
6 12 8 10 15 12 18 16

Sample Outputs:
24
203

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
MAX = 100001
actual = [i for i in range(MAX + 1)]
for i in range(1, MAX + 1):
    for j in range(2 * i, MAX + 1, i):
        actual[j] -= actual[i]

def main(t):
    n = int(input())
    arr = list(map(int, input().split()))
    counts = [0] * (MAX + 1)
    right = [0] * (MAX + 2)
    for num in arr:
        counts[num] += 1
    for i in range(MAX, -1, -1):
        right[i] = right[i + 1] + counts[i]
    ans = 0
    for div in range(1, MAX + 1):
        pre = 0
        for num in range(div, MAX + 1, div):
            if counts[num] == 0:
                continue
            ans += counts[num] * (counts[num] - 1) // 2 * actual[div] * right[num + 1]
            ans += counts[num] * pre * (counts[num] - 1) // 2 * actual[div]
            ans += counts[num] * pre * actual[div] * right[num + 1]
            if counts[num] > 2:
                ans += counts[num] * (counts[num] - 1) * (counts[num] - 2) // 6 * actual[div]
            pre += counts[num]
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import sys
import functools
input = sys.stdin.readline
t = int(input())
for i in range(t):
    n = int(input())
    a = sorted(map(int, input().split()))
    count = [0 for i in range(100001)]
    dp = [0 for i in range(100001)]
    for j in range(n):
        num = a[j]
        d = 1
        while d * d <= num:
            if num % d == 0:
                dp[d] += (n - j - 1) * count[d]
                count[d] += 1
                if d * d != num:
                    dp[num // d] += (n - j - 1) * count[num // d]
                    count[num // d] += 1
            d += 1
    ans = 0
    for j in range(100000, 0, -1):
        for k in range(j + j, 100001, j):
            dp[j] -= dp[k]
        ans += dp[j] * j
    print(ans)

Solution (Python):
def nC2(x):
    return x * (x - 1) // 2

def nC3(x):
    return x * (x - 1) * (x - 2) // 6

def main():
    tests = int(input())
    for _ in range(tests):
        N = 100005
        f = [0] * (N + 5)
        cnt = [0] * (N + 5)
        dp = [0] * (N + 5)
        n = int(input())
        nums = list(map(int, input().split()))
        for x in nums:
            f[x] += 1
        for i in range(N, 0, -1):
            cnt[i] = f[i] + cnt[i + 1]
        ans = 0
        for g in range(N - 1, 0, -1):
            less = 0
            for i in range(g, N, g):
                dp[g] -= dp[i]
                dp[g] += 1 * less * f[i] * cnt[i + 1]
                dp[g] += nC2(f[i]) * less
                dp[g] += nC2(f[i]) * cnt[i + 1]
                dp[g] += nC3(f[i])
                less += f[i]
            ans += dp[g] * g
        print(ans)
if __name__ == '__main__':
    main()