题解 | #约数的个数#

这道题思想不难，判断一个数n的约数的个数，不需要从1遍历到n，只需要从1遍历到sqrt(n)，因为每有一个小于sqrt(n)的因子，相对应的都会有一个大于sqrt(n)的因子。了解思想后，看下面的代码：

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

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; i++) cin >> arr[i];

    for(int i = 0; i < n; i++){
        if(arr[i] == 1){
            cout << 1 << '\n';
            continue;
        }

        int num = arr[i];
        int s = sqrt(num);
        int ans = 0;
        for(int i = 1; i < s; i++){
            if(num % i == 0){
                ans += 2;
            }
        }
        if(num % s == 0) ans ++;
        cout << ans << '\n';
    }
}

这个代码正是运用了上述思想，但是它存在问题，因为int s = sqrt(num)，那么s <= sqrt(num)，也就是说有时s是小于sqrt(num)的（因为sqrt(num)到Int型，去掉小数点后的数），这就导致 i 其实是小于 sqrt(num)的，却没有遍历到。比如说num = 3，sqrt(3)约等于1.7，而int s = sqrt(num)后，s = 1，这就导致是3的约数的1压根都没能遍历，所以需要改进，改进如下：

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

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    for (int i = 0; i < n; i++) {
        if (arr[i] == 1) {
            cout << 1 << '\n';
            continue;
        }

        int num = arr[i];
        int ans = 0;
        int j;
        for (j = 1; j * j < num; j++) {
            if (num % j == 0) {
                ans += 2;
            }
        }
        if (j * j == num) ans++;
        cout << ans << '\n';
    }
}
// 64 位输出请用 printf("%lld")

我们让每个数j，判断j * j是否小于num，这样就没有因为sqrt(num)转到int型时的不精确导致的错误了