计算出 1到 n 之间所有数的因子求和的值,n <= 1e14.C++代码

以下是C++代码实现：

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

typedef long long LL;

LL n; // 题目中的 n

LL get_sum_of_divisors(LL x) {
    LL res = 0;
    for (LL i = 1; i <= sqrt(x); i++) {
        if (x % i == 0) {
            res += i;
            if (i != x / i) {
                res += x / i;
            }
        }
    }
    return res;
}

int main() {
    scanf("%lld", &n);
    LL res = 0;
    for (LL i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            res += i * get_sum_of_divisors(n / i);
            if (i != n / i) {
                res += (n / i) * get_sum_of_divisors(i);
            }
        }
    }
    printf("%lld\n", res);
    return 0;
}

算法思路：

首先，我们可以把 $1$ 到 $n$ 的所有数分解质因数，然后根据每个数分解出的质因数求出它的因子，并对因子求和。

但是这个算法时间复杂度为 $O(n \log n)$，显然无法通过此题。

我们可以优化这个算法，对于每个数 $x$，我们可以枚举它的因子 $i$，然后 $x/i$ 也是它的因子之一，所以可以直接在枚举因子的同时计算它的因子之和，时间复杂度为 $O(\sqrt{n} \log n)$，可以通过此题。