<style>
html, body, .ui-content {
background-image: url(https://truth.bahamut.com.tw/s01/201508/7f0e4bd0e01135c9df434733e0d1544a.JPG);
background-color: #333;
color: #DDD;
}
</style>

###### tags: `Meowmeow Online Judge`

# Counting Coprime Pairs

## Description
Given a list of $n$ positive integers, your task is to count the number of pairs of integers that are coprime (i.e. their greatest common divisor is one).

## Input
The first line has a integer $n$: the number of elements.

The next line has nn integers $x_1$, $x_2$, $\cdots$, $x_nx$ : the contents of the list.

$1≤n≤10^5$
$1≤x≤10^6$

## Output
Print the the number of pairs of integers that are coprime.

## 解題思路
用inclution exclusion計算每一個$x_i$的comprime pairs數
總和再除以2即是答案
:::info
:bulb:**Example:** $30 = 2 * 3 * 5$，所以30的coprime pairs數為list裡
2的倍數 + 3的倍數 + 5的倍數 - 6的倍數 - 10的倍數 - 15的倍數 + 30的倍數
:::
為此要先計算每個數的倍數有幾個，可以先記錄每個數出現了幾次，再計算每個數有幾個倍數
### 時間複雜度
計算出現幾次$O(n)$
計算倍數數量$O(n\ lg\ n)$
計算pair數 $\simeq O(n\sqrt n)$
總時間複雜度$O(n\sqrt n)$

## Code

#include <iostream>
#include <vector>

int number_of_elements;
std::vector<int> inputlist(1000001, 0);
std::vector<int> inpucounter(1000001, 0);
std::vector<int> factorcounter(1000001, 0);
std::vector< std::vector<int> > factorizationtable(1000001);
void input() {
	std::cin >> number_of_elements;
	for (int i = 0; i < number_of_elements; i++)
		std::cin >> inputlist[i];
}
void countInput() {
	for (int i = 0; i < number_of_elements; i++)
		inpucounter[inputlist[i]]++;
}
void countFactor() {
	for (int i = 1; i <= 1000000; i++) {
		for (int j = i; j <= 1000000; j += i) {
			factorcounter[i] += inpucounter[j];
		}
	}
}
std::vector<int> factorization(int digit) {
    if (factorizationtable[digit].size()) return factorizationtable[digit];
	std::vector<int> factor;
    int n = digit;
	for (long long i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			while (n % i == 0)
				n /= i;
			factor.emplace_back(i);
		}
	}
	if (n != 1) factor.emplace_back(n);
    factorizationtable[digit] = factor;
	return factorizationtable[digit];
}
long long int countCoprime(int a) {
	if (a == 1) return number_of_elements - 1;
	int number_of_coprime = 0;
	std::vector<int> factor = factorization(a);
	unsigned S = (1u << factor.size());
	for (unsigned subset = 0; subset < S; subset++) {
		int flag = 1;
		long long int product = 1;
		for (size_t i = 0; i < factor.size(); i++) {
			if ((subset >> i) & 1) {
				flag *= -1;
				product *= factor[i];
			}
		}
		number_of_coprime += flag * factorcounter[product];
	}
	return number_of_coprime;
}
int main() {
	input();
	countInput();
	countFactor();
	/* for (int i = 1; i <= 30; i++) { std::cout << inpucounter[i]; if (i % 5 == 0) std::cout << std::endl;}
	std::cout << std::endl;
	for (int i = 1; i <= 30; i++) { std::cout << factorcounter[i]; if (i % 5 == 0) std::cout << std::endl;}
	std::cout << std::endl; */
	long long int answer = 0;
	for (int i = 0; i < number_of_elements; i++)
		answer += countCoprime(inputlist[i]);
	std::cout << answer / 2 << std::endl;
	return 0;
}