CSES Problem Set — Counting Divisors 題解
===

題目
---
給 $n$ 個正整數，你的任務是回報各個正整數的正因數個數。

例如，當 $x = 18$，正確答案就是 $6$，因為 $x$ 的因數是 $1$、$2$、$3$、$6$、$9$、$18$。

### 輸入
- 第一行輸入一個整數 $n$，代表整數的個數。（$1 \le n \le 10^5$）
- 接著有 $n$ 行，每一行有一個正整數 $x$。（$1 \le x \le 10^6$）

### 輸出
對每個正整數，輸出它的正因數個數。

範例測資
---

Input :
3
16
17
18

Output :
5
2
6

想法：直接計算正因數個數
---
對於正整數 $x$，我們可以直接嘗試除以那些比 $x$ 小的正整數，如果可以除盡（餘數為 $0$），那 $a$ 就是 $x$ 的正因數。

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

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

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

### 範例程式碼

#include <iostream>
using namespace std;

int countDivisors(int x) {
    int cnt = 0;
    for (int a = 1; a*a <= x; a++) {
        if (x % a != 0)
            continue;
        if (x / a != a)
            cnt += 2;
        else
            cnt += 1;
    }
    return cnt;
}

int main() {
    int n, x;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        cout << countDivisors(x) << '\n';
    }
}

想法：先把題目範圍的所有正因數個數計算好
---
我們也可以先算好題目範圍的所有答案並儲存在一個列表中。這麼做就不需要一個個試除，而是直接從因數的角度把它所有的倍數都加一。也就是說，依序做下面的事情：
1. 把所有整數的正因數個數加一
2. 把所有偶數的正因數個數加一
3. 把所有 $3$ 的倍數的正因數個數加一
4. 把所有 $4$ 的倍數的正因數個數加一
5. 以此類推……

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

### 範例程式碼

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

int divisorCount[N];

int main() {
    int n, x;

    for (int a = 1; a < N; a++)
        for (int ka = a; ka < N; ka += a)
            divisorCount[ka] += 1;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        cout << divisorCount[x] << '\n';
    }
}