题解 | 约数的个数

简单的查找。

毫无疑问这道题可以遍历。然而每个数的最大值可以达到 $10^9$ ，显然每个数都遍历一定会超过时间限制（1秒）。因此考虑数学结论。

我们知道任何一个数的每个因数都会对应且仅对应另一个因数。这是因为，因数的本质是整除关系——若 $n$ 有因数 $m$ ，则一定有 $\frac{n}{m}=k\in\mathbb{N_+}$ ，也就是 $mk=n$ ；因此 $k$ 一定也是 $n$ 的因数。所以，任何一个数 $n$ 的因数在 $\sqrt{n}$ 左右两边的个数一定相等。因此，我们只要讨论正整数集合 $\mathbb{N}^*_{\lceil\sqrt{n}\rceil}$ 中所有能整除 $n$ 的数的个数，并在最后乘以2即可。

特别地，如果这个数是完全平方数，那么 $\sqrt{n}$ 也可以整除 $n$ ；这个值并不包括在正整数集合 $\mathbb{N}^*_{\lceil\sqrt{n}\rceil}$ 中，因此最终结果相应地需要加1。

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_DEPRECATE

bool isCompleteSquare(int n) {
    // 判断完全平方数
    for (int i = 1; i <= (int)std::sqrt(n); i++) {
        if (i * i == n) return true;
    }
    return false;
}

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        int searchNumber;
        int count = 0;
        std::cin >> searchNumber;
        for (int i = 1; i < std::sqrt(searchNumber); i++) {
            if (!(searchNumber % i)) count += 2;
        }
        if (isCompleteSquare(searchNumber)) count++;
        std::cout << count << std::endl;
    }
    return 0;
}