P1403

asd890123 · 2024-06-26 20:58:24 · 题解

暴力枚举，代码就不贴了.

就是常用的枚举约数法，枚举到\sqrt n，但同时判断一下n/i是否符合即可:

int f(int x){

    int ans = 0;

    for (int i = 1;i * i <= x;i++)
        if (x % i == 0){

            ans++;
            if (i != x / i) ans++;

        }

    return ans;
}

同复杂度，但可AC做法：

其实约数个数还用一种表达方法就是把x分解素因数，然后把指数加一后相乘，code：

int f(int x){

    int ans = 1;

    for (int i = 2;i * i <= x;i++){

        int cnt = 0;

        while (x % i == 0) x /= i,cnt++;
        ans *= cnt + 1;

    }
    if (x != 1) ans *= 2;

    return ans;
}

正解：

1:O(n\log_2n)

求一串数通常可以用“筛法”，本题也是一样，枚举1到n，并把他们1到n的倍数对应的位置+1即可，也就是“筛”去他们的倍数，核心代码：

for (int i = 1;i <= n;i++)
        for (int j = i;j <= n;j += i)
            f[j]++;

2:O(n)

本题只要求和，所以可以将前面的位置+1，换成ans+1，然后内层循环次数是可以算出的，就是\frac{n}{i}次,code：

for (int i = 1;i <= n;i++) ans += n / i;

3:O(\sqrt n)

这个很容易想到除法分块，贴一下完整代码吧：

#include <iostream>

int main(){

    std::cin.tie(0)->sync_with_stdio(0);

    int n;
    long ans = 0;

    std::cin >> n;
    for (int i = 1,j;i <= n;i = j + 1)
        j = n / (n / i),ans += (n / i) * (j - i + 1);
    std::cout << ans << '\n';

    return 0;
}