## [題目連結](https://cses.fi/problemset/task/2417)
先備知識: [狄利克雷卷積](https://oi-wiki.org/math/poly/dgf/#dirichlet-%E5%8D%B7%E7%A7%AF)跟[積性函數](https://oi-wiki.org/math/number-theory/basic/#%E7%A7%AF%E6%80%A7%E5%87%BD%E6%95%B0)

## 題目敘述
給你一組長度為 $n$ 數字，請找出有幾組互質的數？
- $1 \le n \le 10^5$
- $1 \le x_i \le 10^6$

## 解法
### 1. 先將題目問題化成數學式

$\sum_{i=0}^{n} \sum_{j=i+1}^{n} [\gcd(a_i,a_j)=1]$

這邊中括號代表括號內成立時為 $1$，反之為 $0$

在積性函數中有個東西叫 $\epsilon(x)$，正好可以描述這個數學式
所以可以變換成:

$= \sum\limits_{i=0}^{n} \sum\limits_{j=i+1}^{n} \epsilon(\gcd(a_i,a_j))$

因為 $\mu \ast 1 = \epsilon$，可以推得

$= \sum\limits_{i=0}^{n} \sum\limits_{j=i+1}^{n} \sum\limits_{d\mid \gcd(a_i,a_j)} \mu(d)$

變換求和順序，先枚舉 $d\mid \gcd(a_i,a_j)$ 可得

$= \sum_\limits{d=1}^{\infty} \mu(d) \sum_\limits{i=0}^{n} [d\mid a_i] \sum_\limits{j=i+1}^{n} [d\mid a_j]$

觀察一下，可以發現後面兩個 $\sum$ 就是**有幾對可以被 $d$ 整除**

$= \sum_\limits{d=1}^{a_{max}} \mu(d) \cdot \text{有幾對可以被}\ d\ \text{整除}$

### 2. 線性篩莫比烏斯函數
模板:

void init(vector<int> &mobius, int mx) {
    mobius.resize(mx + 1, 0);
    mobius[1] = 1;
    vector<int> wei(mx + 1);  // wei = 0 代表是質數，-1 代表可被平方數整除
    for (int i = 2; i <= mx; i++) {
        if (wei[i] == -1) {
            mobius[i] = 0;
            continue; // 包含平方
        }
        if (wei[i] == 0) {
            wei[i] = 1;
            for (int j = 2; i * j <= mx; j++) {
                if (j % i == 0) wei[i * j] = -1;
                else if (wei[i * j] != -1) wei[i * j]++;
            }
        }
        mobius[i] = wei[i] % 2 == 0 ? 1 : -1;
    }
}

### 3. 算有幾對可以被 $d$ 整除
這是排列組合的問題，我們可以把問題簡化成，有幾個可以被 $d$ 整除
直接線性篩是會 $TLE$ 的，複雜度 $O(nx\sqrt{x})$

#### 解法:
對 $x_{max}$ 線性篩，用一個陣列看數字 $x$ 有幾個，這樣會是 $O(x\sqrt{x})$
#### 實作:

int n; cin >> n;
vector<int> v(n), mobius;
for (int i = 0; i < n; i++) {
    cin >> v[i];
}
int mx = *max_element(all(v));
vector<int> p(mx + 1);
init(mobius, mx);
for (auto i : v) p[i]++;
for (int i = 1; i <= mx; i++) {
    for (int j = 2; i * j <= mx; j++) {
        p[i] += p[i * j];
    }
}

然後排列組合

for (auto &x : p) x = x * (x - 1) / 2;

## [扣](https://cses.fi/paste/4b5793d530e23cfb8d5868/)