Read problem statements in [Russian], [Mandarin Chinese], [Bengali], and [Vietnamese] as well.

Let's define a function F(X) as follows: 

F(X) = \frac{X}{Y} 

where Y is the largest perfect square that divides X. 

For example,
The largest perfect square that divides 12 is 4. Hence F(12) =  \frac{12}{4} = 3.
The largest perfect square that divides 36 is 36. Hence F(36) =  \frac{36}{36} = 1.
The largest perfect square that divides 7 is 1. Hence F(7) =  \frac{7}{1} = 7.

You are given an array A consisting of N integers. A pair of integer (i, j) is called *Good* if 1 ≤ i < j ≤ N and  F(A_{i} * A_{j}) > 1. Find the number of *Good* pairs.

------ Input Format ------ 

- The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N.
- The second line of each testcase contains N space-separated integers A_{1}, A_{2}, \dots , A_{N}. 

------ Output Format ------ 

For each test case, print a single line containing one integer - the number of *Good* pairs.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$
- The sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
3
3
2 3 12
4 
1 2 3 4
3
2 3 7
----- Sample Output 1 ------ 
2
5
3
----- explanation 1 ------ 
Test case $1$: 
- $(i = 1, j = 2)$: $F(A_{1} * A_{2}) = F(2 * 3) = F(6) = \frac{6}{1} = 6 > 1$. 
- $(i = 1, j = 3)$: $F(A_{1} * A_{3}) = F(2 *12) = F(24) = \frac{24}{4} = 6 > 1$.
- $(i = 2, j = 3)$: $F(A_{2} * A_{3}) = F(3 *12) = F(36) = \frac{36}{36} = 1 \ngtr 1$.

So there are 2 Good pairs.

Test case $2$:  All pairs except ($1, 4$) are Good pairs as $F(A_{1} * A_{4}) = F(1 * 4) = F(4) = \frac{4}{4} = 1 \ngtr 1$. 

Test case $3$:  All pairs are Good pairs.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Mathematics


Solutions:
t = 10 ** 6 + 1
prime = [0] * t
k = [0] * t

def sieve():
	for i in range(1, t):
		k[i] = i
	for i in range(2, t):
		if prime[i] == 0:
			for j in range(i, t, i):
				prime[j] = 1
				while k[j] % (i * i) == 0:
					k[j] /= i * i

def count_pair(arr, n):
	freq = {}
	for i in range(n):
		if k[arr[i]] in freq.keys():
			freq[k[arr[i]]] += 1
		else:
			freq[k[arr[i]]] = 1
	res = 0
	for i in freq:
		res += freq[i] * (freq[i] - 1) // 2
	return res
sieve()
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	temp = count_pair(arr, n)
	all_pair = n * (n - 1) // 2
	print(all_pair - temp)


MAX = 10 ** 6 + 42
lp = [0] * MAX
for i in range(2, MAX):
	for j in range(i, MAX, i):
		if lp[j] == 0:
			lp[j] = i

def solve_case():
	n = int(input())
	a = [int(x) for x in input().split()]
	cnt = dict()
	ans = n * (n - 1) // 2
	for x in a:
		v = 1
		squarefree_list = []
		while x > 1:
			flag = 0
			d = lp[x]
			while x % d == 0:
				flag ^= 1
				x //= d
			if flag:
				squarefree_list.append(d)
		squarefree_list = tuple(squarefree_list)
		if squarefree_list not in cnt:
			cnt[squarefree_list] = 0
		ans -= cnt[squarefree_list]
		cnt[squarefree_list] += 1
	print(ans)
cases = int(input())
for _ in range(cases):
	solve_case()


from collections import Counter
N = 10 ** 6
init = [1] * N
for i in range(1, 10 ** 3 + 1):
	x = i * i
	for j in range(x, N + 1, x):
		init[j - 1] = x
t = int(input())
for _ in range(t):
	(n, a) = (int(input()), [int(x) for x in input().split()])
	c = Counter((x // init[x - 1] for x in a))
	print(n * (n - 1) // 2 - sum((c[x] * (c[x] - 1) // 2 for x in c)))


prime = [0] * 1000001
k = [0] * 1000001

def Sieve():
	for i in range(1, 1000001):
		k[i] = i
	for i in range(2, 1000001):
		if prime[i] == 0:
			for j in range(i, 1000001, i):
				prime[j] = 1
				while k[j] % (i * i) == 0:
					k[j] /= i * i

def countPairs(arr, n, freq):
	for i in range(n):
		freq[k[arr[i]]] = freq[k[arr[i]]] + 1 if k[arr[i]] in freq.keys() else 1
	return sum([freq[i] * (freq[i] - 1) // 2 for i in freq])
Sieve()
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	print(n * (n - 1) // 2 - countPairs(arr, n, dict()))


import math
MAX_NUMBER = 10 ** 6 + 1
spf = [0] * MAX_NUMBER

def nCr(n, r):
	return fact(n) / (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def seives():
	spf[1] = 1
	for i in range(2, MAX_NUMBER):
		spf[i] = i
	for i in range(4, MAX_NUMBER, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAX_NUMBER))):
		if spf[i] == i:
			for j in range(i * i, MAX_NUMBER, i):
				if spf[j] == j:
					spf[j] = i

def solve(arr, n):
	odd_factors = {}
	total_odd_each = {}
	for j in range(0, n):
		x = arr[j]
		while x != 1:
			if spf[x] not in odd_factors.keys():
				odd_factors[spf[x]] = 1
			else:
				odd_factors[spf[x]] = odd_factors[spf[x]] + 1
			x = x // spf[x]
		m = 1
		for k in odd_factors.keys():
			if odd_factors[k] % 2 != 0:
				m = m * k
		if m not in total_odd_each.keys():
			total_odd_each[m] = 1
		else:
			total_odd_each[m] = total_odd_each[m] + 1
		odd_factors = {}
	return total_odd_each
seives()
test = int(input())
for i in range(0, test):
	n = int(input())
	arr = list(map(int, input().split()))
	f = solve(arr, n)
	counter = 0
	for j in f.keys():
		counter = counter + int(nCr(f[j], 2))
	z = n * (n - 1) // 2
	print(z - counter)


import sys
prime = [0] * 1000001
k = [0] * 1000001

def k_array():
	for i in range(1, 1000001):
		k[i] = i
	for i in range(2, 1000001):
		if prime[i] == 0:
			for j in range(i, 1000001, i):
				prime[j] = 1
				while k[j] % (i * i) == 0:
					k[j] /= i * i

def countPairs(arr, num):
	freq = dict()
	for i in range(n):
		if k[arr[i]] in freq.keys():
			freq[k[arr[i]]] += 1
		else:
			freq[k[arr[i]]] = 1
	Sum = 0
	for i in freq.keys():
		Sum += freq[i] * (freq[i] - 1) / 2
	return Sum
k_array()
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, sys.stdin.readline().split()))
	ans = int(n * (n - 1) // 2)
	ans -= int(countPairs(arr, n))
	print(ans)


init = 1000001
pr = [0] * init
redu = [0] * init

def PreProcess():
	for i in range(1, init):
		redu[i] = i
	for i in range(2, init):
		if pr[i] == 0:
			for j in range(i, init, i):
				pr[j] = 1
				while redu[j] % (i * i) == 0:
					redu[j] /= i * i

def pairs(arr, n):
	dic = dict()
	for i in range(n):
		if redu[arr[i]] in dic.keys():
			dic[redu[arr[i]]] += 1
		else:
			dic[redu[arr[i]]] = 1
	sumi = 0
	for i in dic:
		sumi += dic[i] * (dic[i] - 1) / 2
	return sumi
PreProcess()
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	cnt = n * (n - 1) // 2
	cnt -= int(pairs(arr, n))
	print(cnt)


import sys
prime = [0] * 1000001
k = [0] * 1000001

def Sieve():
	for i in range(1, 1000001):
		k[i] = i
	for i in range(2, 1000001):
		if prime[i] == 0:
			for j in range(i, 1000001, i):
				prime[j] = 1
				while k[j] % (i * i) == 0:
					k[j] /= i * i

def countPairs(arr, n):
	freq = dict()
	for i in range(n):
		if k[arr[i]] in freq.keys():
			freq[k[arr[i]]] += 1
		else:
			freq[k[arr[i]]] = 1
	Sum = 0
	for i in freq:
		Sum += freq[i] * (freq[i] - 1) / 2
	return Sum
Sieve()
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	ans = int(n * (n - 1) // 2)
	ans -= int(countPairs(arr, n))
	print(ans)


import collections
import math as mt
MAXN = 1000001
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret
sieve()

def get_rem(b):
	r = collections.Counter(getFactorization(b))
	t = 1
	for i in r:
		if r[i] % 2 != 0:
			t = t * i
	return t
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dec = {}
	dec[get_rem(a[0])] = 1
	res = 0
	for i in range(1, n):
		r = get_rem(a[i])
		if r in dec:
			res += dec[r]
			dec[r] += 1
		else:
			dec[r] = 1
	print(n * (n - 1) // 2 - res)


max_arr = 10 ** 6 + 1
prime = [0] * max_arr
k = [0] * max_arr

def sieve():
	for i in range(1, max_arr):
		k[i] = i
	for i in range(2, max_arr):
		if prime[i] == 0:
			for j in range(i, max_arr, i):
				prime[j] = 1
				while k[j] % (i * i) == 0:
					k[j] //= i * i

def countPairs(arr, n):
	freq = dict()
	for i in range(n):
		if k[arr[i]] in freq.keys():
			freq[k[arr[i]]] += 1
		else:
			freq[k[arr[i]]] = 1
	Sum = 0
	for i in freq:
		Sum += freq[i] * (freq[i] - 1) // 2
	return Sum
sieve()
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	all_pairs = n * (n - 1) // 2
	good_pairs = countPairs(arr, n)
	print(all_pairs - good_pairs)


MAX_LTS = 10 ** 6
lts = [1] * (MAX_LTS + 1)
for i in range(2, MAX_LTS + 1):
	if lts[i] == 1:
		for j in range(i, MAX_LTS + 1, i):
			lts[j] = i
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = N * (N - 1) // 2
	LP = {}
	for i in range(N):
		a = A[i]
		lp = 1
		h = 1
		while a > 1:
			l = lts[a]
			if l == h:
				h = 1
			elif h == 1:
				h = l
			else:
				lp *= h
				h = l
			a //= l
		lp *= h
		LP[lp] = LP.get(lp, 0) + 1
	for (a, b) in LP.items():
		if b > 1:
			ans -= b * (b - 1) // 2
	print(ans)


def sieve():
	primes = [i for i in range(10 ** 6 + 1)]
	primes[0] = -1
	primes[1] = -1
	i = 2
	while i * i <= 10 ** 6:
		if primes[i] == i:
			j = i * i
			while j <= 10 ** 6:
				primes[j] = i
				j += i
		i += 1
	return primes
t = int(input())
Q = sieve()
for i in range(0, t):
	n = int(input())
	L = list(map(int, input().split()))
	dic = {}
	for j in range(0, n):
		temp = L[j]
		d1 = {}
		while temp != 1:
			qt = Q[temp]
			temp = temp // qt
			if qt not in d1:
				d1[qt] = 1
			else:
				d1[qt] = (d1[qt] + 1) % 2
		pro = 1
		for u in d1:
			if d1[u] == 1:
				pro = pro * u
		L[j] = pro
	for u in L:
		if u not in dic:
			dic[u] = 1
		else:
			dic[u] += 1
	tot = n * (n - 1) // 2
	for e in dic.keys():
		s0 = dic[e]
		s1 = s0 * (s0 - 1) // 2
		tot -= s1
	print(tot)


prime = [0] * 1000001
k = [0] * 1000001

def Sieve():
	for i in range(1, 1000001):
		k[i] = i
	for i in range(2, 1000001):
		if prime[i] == 0:
			for j in range(i, 1000001, i):
				prime[j] = 1
				while k[j] % (i * i) == 0:
					k[j] /= i * i

def countPairs(arr, n):
	freq = dict()
	for i in range(n):
		if k[arr[i]] in freq.keys():
			freq[k[arr[i]]] += 1
		else:
			freq[k[arr[i]]] = 1
	Sum = 0
	for i in freq:
		Sum += freq[i] * (freq[i] - 1) / 2
	return Sum
t = int(input())
Sieve()
while t > 0:
	t -= 1
	n = int(input())
	tot = n * (n - 1) // 2
	arr = [int(x) for x in input().split()]
	print(int(tot) - int(countPairs(arr, n)))