Magic Triples (Hard Version) (Codeforces 1822G2)
Tags: Math, number theory

This is the hard version of the problem. The only difference is that in this version, $$$a_i \le 10^9$$$.For a given sequence of $$$n$$$ integers $$$a$$$, a triple $$$(i, j, k)$$$ is called magic if:   $$$1 \le i, j, k \le n$$$.  $$$i$$$, $$$j$$$, $$$k$$$ are pairwise distinct.  there exists a positive integer $$$b$$$ such that $$$a_i \cdot b = a_j$$$ and $$$a_j \cdot b = a_k$$$. Kolya received a sequence of integers $$$a$$$ as a gift and now wants to count the number of magic triples for it. Help him with this task!Note that there are no constraints on the order of integers $$$i$$$, $$$j$$$ and $$$k$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of the test case contains a single integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the length of the sequence.The second line of the test contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the sequence $$$a$$$.The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single integer — the number of magic triples for the sequence $$$a$$$.

Note: In the first example, there are $$$6$$$ magic triples for the sequence $$$a$$$ — $$$(2, 3, 5)$$$, $$$(2, 5, 3)$$$, $$$(3, 2, 5)$$$, $$$(3, 5, 2)$$$, $$$(5, 2, 3)$$$, $$$(5, 3, 2)$$$.In the second example, there is a single magic triple for the sequence $$$a$$$ — $$$(2, 1, 3)$$$.

Sample Inputs:
7
5
1 7 7 2 7
3
6 2 18
9
1 2 3 4 5 6 7 8 9
4
1000 993 986 179
7
1 10 100 1000 10000 100000 1000000
8
1 1 2 2 4 4 8 8
9
1 1 1 2 2 2 4 4 4

Sample Outputs:
6
1
3
0
9
16
45

Solution (Python):
from io import BytesIO, IOBase
import sys
import os
import bisect, collections, copy, heapq, itertools, math, sys
import time
import bisect
import functools
import math
import random
import re
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *

def main():

    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')
    BUFSIZE = 4096

    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 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))

        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()
    sys.stdin = IOWrapper(sys.stdin)
    sys.stdout = IOWrapper(sys.stdout)
    input = sys.stdin.readline

    def I():
        return input()

    def II():
        return int(input())

    def MII():
        return map(int, input().split())

    def LI():
        return list(input().split())

    def LII():
        return list(map(int, input().split()))

    def GMI():
        return map(lambda x: int(x) - 1, input().split())

    def LGMI():
        return list(map(lambda x: int(x) - 1, input().split()))
    inf = float('inf')

    class SegmentTree:

        def __init__(self, data, merge):

            def _build(tree_index, l, r):
                if l == r:
                    self.tree[tree_index] = data[l]
                    return
                mid = (l + r) // 2
                (left, right) = (2 * tree_index + 1, 2 * tree_index + 2)
                _build(left, l, mid)
                _build(right, mid + 1, r)
                self.tree[tree_index] = self._merge(self.tree[left], self.tree[right])
            self.n = len(data)
            self.tree = [None for _ in range(4 * self.n)]
            self._merge = merge
            _build(0, 0, self.n - 1)

        def query(self, ql, qr):
            return self._query(0, 0, self.n - 1, ql, qr)

        def _query(self, tree_index, l, r, ql, qr):
            if l == ql and r == qr:
                return self.tree[tree_index]
            mid = (l + r) // 2
            (left, right) = (tree_index * 2 + 1, tree_index * 2 + 2)
            if qr <= mid:
                return self._query(left, l, mid, ql, qr)
            elif ql > mid:
                return self._query(right, mid + 1, r, ql, qr)
            return self._merge(self._query(left, l, mid, ql, mid), self._query(right, mid + 1, r, mid + 1, qr))

        def update(self, index, value):

            def _update(tree_index, l, r, index):
                if l == r == index:
                    self.tree[tree_index] = value
                    return
                mid = (l + r) // 2
                (left, right) = (2 * tree_index + 1, 2 * tree_index + 2)
                if index > mid:
                    _update(right, mid + 1, r, index)
                else:
                    _update(left, l, mid, index)
                self.tree[tree_index] = self._merge(self.tree[left], self.tree[right])
            _update(0, 0, self.n - 1, index)

    def merge(lst1, lst2):
        return max(lst1, lst2)
    primes = []
    vis = [0] * 1050
    for i in range(2, 1050):
        if not vis[i]:
            primes.append(i)
            for idx in range(i, 1050, i):
                vis[idx] = 1
    t = II()
    for _ in range(t):
        n = II()
        nums = LII()
        cnt = Counter(sorted(nums))
        ans = 0
        for x in cnt:
            ans += cnt[x] * (cnt[x] - 1) * (cnt[x] - 2)
            v = x
            tmp = []
            for p in primes:
                c = 0
                while v % p == 0:
                    v //= p
                    c += 1
                if c // 2:
                    tmp.append([p, c // 2])
            r = round(v ** 0.5)
            if r > 1 and v == r * r:
                tmp.append([r, 1])
            factors = [1]
            for (p, b) in tmp:
                n = len(factors)
                for j in range(1, b + 1):
                    for d in factors[:n]:
                        factors.append(d * p ** j)
            for f in factors:
                if f > 1 and x // f in cnt and (x // f // f in cnt):
                    ans += cnt[x] * cnt[x // f] * cnt[x // f // f]
        print(ans)
main()

Solution (Python):
""""""
maxN = 1001
sieve = list(range(maxN))
for i in range(2, maxN):
    if sieve[i] == i:
        for j in range(2 * i, maxN, i):
            sieve[j] = i
primes = [i for i in range(2, maxN) if sieve[i] == i]

def get_square_factors(x):
    pc = []
    for p in primes:
        cnt = 0
        while x % p == 0:
            x //= p
            cnt += 1
        if cnt > 0:
            pc.append((p, cnt))
    if x > 1:
        sqrt = int(x ** 0.5)
        if sqrt * sqrt == x:
            pc.append((sqrt, 2))
    factors = [1]
    for (p, c) in pc:
        factors2 = factors.copy()
        for c2 in range(2, c + 1, 2):
            for f in factors:
                factors2.append(f * p ** c2)
        factors = factors2
    return factors
from collections import Counter

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        a.sort()
        cnts = Counter(a)
        ans = 0
        for (x, c) in cnts.items():
            factors = get_square_factors(x)
            for d2 in factors:
                if d2 != 1:
                    d = int(d2 ** 0.5)
                    ans += cnts[x] * cnts[x // d] * cnts[x // d2]
            if c >= 3:
                ans += c * (c - 1) * (c - 2)
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
def get_count_func(a):
    n = len(a)
    a.sort()
    cnts = dict()
    c = 0
    for i in range(n):
        c += 1
        if not (i + 1 < n and a[i] == a[i + 1]):
            cnts[a[i]] = c
            c = 0

    def count_func(x):
        if x in cnts.keys():
            return cnts[x]
        else:
            return 0
    return count_func
''

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        MAX_A = max(a)
        bound = int(MAX_A ** (2 / 3))
        count_func = get_count_func(a)
        ans = 0
        for (i, x) in enumerate(a):
            if x >= bound:
                d = 2
                while x * d <= MAX_A:
                    if x % d == 0:
                        left = x // d
                        right = x * d
                        cl = count_func(left)
                        if cl > 0:
                            cr = count_func(right)
                            if cr > 0:
                                ans += cl * cr
                    d += 1
            else:
                if x != 1:
                    ans += count_func(1) * count_func(x * x)
                d = 2
                while d * d <= x:
                    if x % d == 0:
                        to_check = [d]
                        d2 = x // d
                        if d2 != d:
                            to_check.append(d2)
                        for d3 in to_check:
                            cl = count_func(x // d3)
                            if cl > 0:
                                cr = count_func(x * d3)
                                if cr > 0:
                                    ans += cl * cr
                    d += 1
            if not (i - 1 >= 0 and a[i] == a[i - 1]):
                c = count_func(x)
                if c >= 3:
                    ans += c * (c - 1) * (c - 2)
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()