CSES Problem Set — Common Divisors 題解
===

題目
---
給你一個陣列裝有 $n$ 個正整數，你的任務是找到其中兩個正整數使得它們的最大公因數是最大的。

### 輸入
- 第一行輸入一個整數 $n$，代表陣列的長度。（$2 \le n \le 2 \cdot 10^5$）
- 第二行有 $n$ 個正整數 $x_i$，代表陣列的內容。（$1 \le x_i \le 10^6$）

### 輸出
輸出最大的最大公因數。

範例測資
---

Input :
5
3 14 15 7 9

Output :
7

最大的最大公因數是 $14$ 跟 $7$ 的最大公因數 $\gcd(14, 7) = 7$。

想法：統計題目範圍的正整數是陣列中多少個數字的正因數
---
我們可以用一個列表統計題目範圍的各個正整數 $a$ 是陣列中多少個 $x_i$ 的正因數，如果一個正整數 $a$ 是陣列中兩個以上的 $x_i$ 的正因數，那麼它就是公因數。我們只要找最大的正整數 $a$ 使得它被統計到兩個以上，那麼這個 $a$ 就會是最大的最大公因數。

要做這個統計，我們跑遍陣列裡的各個 $x_i$，並各自嘗試除以題目範圍的每個正整數 $a$。如果可以除盡（餘數為 $0$），那 $a$ 就是 $x_i$ 的正因數，我們就在統計列表中為 $a$ 加一。

我們可以觀察到，如果 $a$ 是 $x_i$ 的正因數，那麼 $\dfrac{x_i}{a}$ 也會是 $x_i$ 的正因數。正因數都是能兩個兩個配對成 $\bigl(a, \dfrac{x_i}{a}\bigr)$ 一組的，除了當 $x_i$ 是完全平方數的時候會有一組 $\bigl(\sqrt{x_i}, \sqrt{x_i}\bigr)$ 是兩個相等的正整數。

總而言之，我們其實嘗試那些不大於 $\sqrt{x_i}$ 的正整數就好。如果找到了正因數 $a < \sqrt{x_i}$，那麼我們就一次找到了兩個相異的正因數 $a$ 與 $\dfrac{x_i}{a}$；而如果找到了正因數 $a = \sqrt{x_i}$ 時，我們就只有找到一個正因數。

因為我們要找的是統計列表中被記錄大於等於 $2$ 最大位置，從有可能的公因數 $\max(x_i)$ 開始往下找第一個大於等於 $2$ 的位置就好。

這個算法的時間複雜度會是 $O(n \cdot \sqrt{\max(x_i)})$。

### 範例程式碼

#include <iostream>
using namespace std;
#define N 1000001

int count[N] = {0};

void countDivisors(int x) {
    for (int a = 1; a*a <= x; a++) {
        if (x % a != 0)
            continue;
        count[a] += 1;
        if (x / a != a)
            count[x / a] += 1;
    }
}

int main() {
    int n, x, m=0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        countDivisors(x);
        if (x > m)
            m = x;
    }
    for (int a = m; a > 0; a--) {
        if (count[a] >= 2) {
            cout << a;
            break;
        }
    }
}

想法：在題目範圍的正整數中看各自有多少倍數在陣列裡
---
我們也可以反過來看題目範圍的所有正整數 $a$ 有多少倍數出現在陣列裡面，如果正整數 $a$ 有兩個以上的倍數出現在陣列裡，那麼 $a$ 就是公因數。我們只要找最大的正整數 $a$ 使得它有兩個以上的倍數出現在陣列裡，那麼這個 $a$ 就會是最大的最大公因數。

我們可以把每個數字出現在陣列的次數先儲存在一個列表中。這麼做就不需要一個個試除，而是直接從因數的角度把它所有倍數出現次數加總。

而且因為我們要找的是最大的正整數 $a$ 使得它有兩個以上的倍數出現在陣列裡，從有可能的公因數 $\max(x_i)$ 開始往下找第一個滿足條件的數字就好。

這個算法的時間複雜度會是 $O(N \log N)$，其中 $N = \max(x_i)$。
> 計算這個複雜度時要注意到調和級數是呈對數增長的：$\displaystyle \sum_{k=1}^N \frac{1}{k} \approx \log N$。

### 範例程式碼

#include <iostream>
using namespace std;
#define N 1000001

int count[N] = {0};

int main() {
    int n, x, m=0, cnt;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        count[x] += 1;
        if (x > m)
            m = x;
    }
    
    for (int a = m; a > 0; a--) {
        cnt = 0;
        for (int ka = a; ka <= m; ka += a) {
            cnt += count[ka];
        }
        if (cnt >= 2) {
            cout << a;
            break;
        }
    }
}