Counting Rhyme (Codeforces 1884D)
Tags: Math, number theory

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$.A pair of integers $$$(i, j)$$$, such that $$$1 \le i < j \le n$$$, is called good, if there does not exist an integer $$$k$$$ ($$$1 \le k \le n$$$) such that $$$a_i$$$ is divisible by $$$a_k$$$ and $$$a_j$$$ is divisible by $$$a_k$$$ at the same time.Please, find the number of good pairs.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, output the number of good pairs.

Note: In the first test case, there are no good pairs. In the second test case, here are all the good pairs: $$$(1, 2)$$$, $$$(2, 3)$$$, and $$$(2, 4)$$$.

Sample Inputs:
6
4
2 4 4 4
4
2 3 4 4
9
6 8 9 4 6 8 9 4 9
9
7 7 4 4 9 9 6 2 9
18
10 18 18 15 14 4 5 6 8 9 10 12 15 16 18 17 13 11
21
12 19 19 18 18 12 2 18 19 12 12 3 12 12 12 18 19 16 18 19 12

Sample Outputs:
0
3
26
26
124
82

Solution (Python):
import decimal
import gc
import heapq
import math
import operator
import os
import random
import sys
from collections import Counter, deque, defaultdict, OrderedDict
from copy import copy
from fractions import Fraction
from io import BytesIO, IOBase
import bisect
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def bucketsort(order, seq):
    buckets = [0] * (max(seq) + 1)
    for x in seq:
        buckets[x] += 1
    for i in range(len(buckets) - 1):
        buckets[i + 1] += buckets[i]
    new_order = [-1] * len(seq)
    for i in reversed(order):
        x = seq[i]
        idx = buckets[x] = buckets[x] - 1
        new_order[idx] = i
    return new_order

def ordersort(order, seq, reverse=False):
    bit = max(seq).bit_length() >> 1
    mask = (1 << bit) - 1
    order = bucketsort(order, [x & mask for x in seq])
    order = bucketsort(order, [x >> bit for x in seq])
    if reverse:
        order.reverse()
    return order

def isPrime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i = i + 6
    return True

def lcm(a, b):
    return a * b // math.gcd(a, b)

def ciel(a, b):
    x = a // b
    if a % b == 0:
        return x
    return x + 1

def ints_get():
    return map(int, input().strip().split())

def list_get():
    return list(map(int, sys.stdin.readline().strip().split()))

def chars_get():
    return list(map(str, sys.stdin.readline().strip().split()))

def ipn():
    return int(input())

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def main():
    for _ in range(ipn()):
        n = ipn()
        a = list_get()
        v = [0] * (n + 1)
        for i in a:
            v[i] += 1
        arr = [0] * (n + 1)
        num = [0] * (n + 1)
        b = [0] * (n + 1)
        res = 0
        for i in range(1, n + 1):
            val = 0
            for j in range(1, 10 ** 9):
                if i * j > n:
                    break
                val += v[i * j]
            if v[i] > 0 or b[i] > 0:
                if arr[i] <= 0:
                    p = 1 - arr[i]
                    for j in range(1, 10 ** 9):
                        if i * j > n:
                            break
                        num[i * j] += p * val
                        arr[i * j] += p
                        b[i * j] = 1
            if arr[i] > 1:
                p = arr[i] - 1
                for j in range(1, 10 ** 9):
                    if i * j > n:
                        break
                    num[i * j] -= p * val
                    arr[i * j] -= p
        for i in range(1, n + 1):
            res += (n - num[i]) * v[i]
        print(res // 2)
    return
if __name__ == '__main__':
    main()

Solution (Python):
import sys
ipt = sys.stdin.readline

def iin():
    return int(ipt())

def lmin():
    return list(map(int, ipt().split()))
for _ in range(iin()):
    N = iin()
    A = lmin()
    cnt = [0] * (N + 1)
    for a in A:
        cnt[a] += 1
    dp = [0] * (N + 1)
    F = [0] * (N + 1)
    for i in range(N, 0, -1):
        s = 0
        t = 0
        for j in range(i, N + 1, i):
            t += dp[j]
            s += cnt[j]
            if cnt[i]:
                F[j] = 1
        dp[i] = s * (s - 1) // 2 - t
    print(N * (N - 1) // 2 - sum((dp[i] for i in range(N + 1) if F[i])))

Solution (Python):
import sys
from collections import Counter
input = lambda : sys.stdin.buffer.readline().decode().rstrip()

def gen(lst):
    res = set()
    for i in range(2 ** len(lst)):
        d = 1
        for j in range(len(lst)):
            if 1 << j & i:
                d *= lst[j]
        res.add(d)
    return res

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    mx = max(arr)
    cnt = [0] * (n + 1)
    for i in arr:
        cnt[i] += 1
    dp = [0] * (mx + 2)
    acc = 0
    for g in range(mx, 0, -1):
        s = 0
        for k in range(int(mx / g), 0, -1):
            tar = g * k
            if cnt[tar]:
                s += cnt[tar]
        dp[g] += s * (s - 1) // 2
        l = 2
        while True:
            try:
                dp[g] -= dp[g * l]
            except:
                break
            l += 1
    ans = n * (n - 1) // 2
    forbid = [0] * (n + 1)
    for i in range(mx, 0, -1):
        if cnt[i] == 0:
            continue
        l = 1
        while True:
            try:
                if not forbid[i * l]:
                    forbid[i * l] = 1
                    ans -= dp[i * l]
            except:
                break
            l += 1
    print(ans)
for t in range(int(input())):
    solve()