Read problems statements in Mandarin Chinese  and Russian. 

You are given a sequence a_{1}, a_{2}, ..., a_{N}. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(a_{i}, a_{j}, a_{k}) = 1. Here GCD stands for the Greatest Common Divisor.

------ Input ------ 

The first line of input contains a single integer N - the length of the sequence.

The second line contains N space-separated integers - a_{1}, a_{2}, ..., a_{N} respectively.

------ Output ------ 

Output the required number of triples on the first line of the output.

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

$1 ≤ N ≤ 100 : 22 points.$
$1 ≤ N ≤ 1000 : 23 points.$
$1 ≤ N ≤ 10^{5} : 55 points.$
$1 ≤ a_{i} ≤ 10^{6}$

------ Example ------ 

Input:
4
1 2 3 4

Output:
4

------ Explanation ------ 

Any triple will be a coprime one.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Mathematics


Solutions:
import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
n = inp()
l = li()
MA = max(l)
count = [0] * (MA + 1)
for i in l:
	count[i] += 1
for i in range(1, MA + 1):
	for j in range(2 * i, MA + 1, i):
		count[i] += count[j]
	count[i] = count[i] * (count[i] - 1) * (count[i] - 2) // 6
for i in range(MA, 0, -1):
	for j in range(2 * i, MA + 1, i):
		count[i] -= count[j]
pr(count[1])


import os.path
from math import *
from collections import *
import sys
n = input()
l = list(map(int, sys.stdin.readline().split()))
m = max(l)
count = [0] * (m + 1)
for i in l:
	count[i] += 1
for i in range(1, m + 1):
	for j in range(2 * i, m + 1, i):
		count[i] += count[j]
	count[i] = count[i] * (count[i] - 1) * (count[i] - 2) // 6
for i in range(m, 0, -1):
	for j in range(2 * i, m + 1, i):
		count[i] -= count[j]
print(count[1])


n = int(input())
l = list(map(int, input().split()))
MA = max(l)
count = [0] * (MA + 1)
for i in l:
	count[i] += 1
for i in range(1, MA + 1):
	for j in range(2 * i, MA + 1, i):
		count[i] += count[j]
	count[i] = count[i] * (count[i] - 1) * (count[i] - 2) // 6
for i in range(MA, 0, -1):
	for j in range(2 * i, MA + 1, i):
		count[i] -= count[j]
print(count[1])


N = 10 ** 6 + 100
sv = [i for i in range(N)]
for i in range(2, N):
	if i * i >= N:
		break
	if sv[i] < i:
		continue
	for j in range(i * i, N, i):
		sv[j] = min(sv[j], i)

def getPrimes(a):
	pr = []
	if a == 1:
		return pr
	pr.append(sv[a])
	while a > 1:
		if sv[a] != pr[-1]:
			pr.append(sv[a])
		a //= sv[a]
	return pr
np = [0] * N
F = [0] * N
n = int(input())
A = list(map(int, input().split()))
for a in A:
	pr = getPrimes(a)
	for i in range(1 << len(pr)):
		(prod, nb) = (1, 0)
		for j in range(len(pr)):
			if i & 1 << j:
				prod *= pr[j]
				nb += 1
		F[prod] += 1
		np[prod] = nb
ans = 0
for i in range(N):
	cnt = F[i]
	cnt = cnt * (cnt - 1) * (cnt - 2) // 6
	if np[i] & 1:
		ans -= cnt
	else:
		ans += cnt
print(ans)


import sys
data = sys.stdin.read().split()
data.reverse()

def read():
	return int(data.pop())

def readStr():
	return data.pop()
N = 10 ** 6 + 100
sv = [i for i in range(N)]
for i in range(2, N):
	if i * i >= N:
		break
	if sv[i] < i:
		continue
	for j in range(i * i, N, i):
		sv[j] = min(sv[j], i)

def getPrimes(a):
	pr = []
	if a == 1:
		return pr
	pr.append(sv[a])
	while a > 1:
		if sv[a] != pr[-1]:
			pr.append(sv[a])
		a //= sv[a]
	return pr
np = [0] * N
F = [0] * N
n = read()
A = [read() for i in range(n)]
for a in A:
	pr = getPrimes(a)
	for i in range(1 << len(pr)):
		(prod, nb) = (1, 0)
		for j in range(len(pr)):
			if i & 1 << j:
				prod *= pr[j]
				nb += 1
		F[prod] += 1
		np[prod] = nb
ans = 0
for i in range(N):
	cnt = F[i]
	cnt = cnt * (cnt - 1) * (cnt - 2) // 6
	if np[i] & 1:
		ans -= cnt
	else:
		ans += cnt
print(ans)