---
tags: CSES題解
---

CSES Problem Set — Counting Coprime Pairs 題解
===

## 題目
給定一個長度為 $n$ 的陣列，求從陣列中任意兩個配對使得他們互質的數量。

### 輸入
第一行有一個正整數 $n$，下一行有 $n$ 個正整數 $a_i$，代表陣列中的第 $i$ 個元素。

### 輸出
輸出互質的配對數。

## 解法一：動態規劃
定義：
- $cnt_i = a_i$ 為 $i$ 的數量
- $dp_i =$ 配對的最大公因數為 $i$ 的數量

根據定義，$dp_1$ 即為題目所求。

我們將從 $10^6$ 處理到 $1$（設目前處理的數字為 $i$）

我們將取出所有 $i$ 的倍數的配對數（共 ${cnt_i \choose 2}$ 個）。

上述的配對最小公因數只可能是 $i, 2i, 3i, \ldots$，由於我們已經算出了 $dp_{2i}, dp_{3i}, \dots$，因此 $dp_i = {{cnt_i} \choose 2} - \sum \limits _{k\ge 2} dp_{ik}$

:::info
註：本技巧在多種因倍數相關的 $dp$ 題相當常見，請留意。
:::

### 時間複雜度
設 $A = 10^6$
我們將枚舉 $i = 1 \sim A$，每次枚舉都會枚舉 $2i, 3i, 4i$，因此總枚舉量為 $\sum \limits _{i=1}^{A} \lfloor \frac{A}{i} \rfloor$，根據調和級數可以知道時間複雜度為 $O(n \log n)$

### 程式碼

#include <bits/stdc++.h>
using namespace std;

int n, tmp;
const int MAX_A = 1e6+10;

vector<int> cnt(MAX_A); // cnt[i] = i 有幾個
vector<int> dp(MAX_A);  // dp[i] = 最大公因數為 i 的 pair 有多少個

int main(){

    // input
    cin >> n;
    for (int i=0 ; i<n ; i++){
        cin >> tmp;
        cnt[tmp]++;
    }

    // process
    for (int i=MAX_A-1 ; i>=1 ; i--){ // 處理每個 i

        int aa = 0, bb = 0; // aa = 所有 i 的倍數的配對數，bb = 最小公因數不是 i 的配對數
        for (int j=i ; j<MAX_A ; j+=i){ // 枚舉所有倍數
            aa += cnt[j];
            bb += dp[j];
        }

        dp[i] = (aa*(aa-1)/2)-bb; // 用排列組合出
    }

    // output
    cout << dp[1] << "\n"; // 根據 dp 定義，dp_1（最大公因數為 1，也就是互質）及為所求

    return 0;
}