c++ - 给定范围内数字因子的最大总和

Question

这是我在一些在线评委平台上做的题。

找出从 1 到 N 的数字的最大因子和。

例如，如果 N 为 11，则答案为 18。从 1 到 11 的因数和最大的数是 10 (1 + 2 + 5 + 10)。

我实现了一个看起来像筛子的相对简单的解决方案。 C++中的代码如下所示:

for (int i = 1; i <= 1000000; ++i {
    for (int j = i; j <= 1000000; j += i) {
        num[j] += i;
    }
    mx[i] = max(num[i], mx[i - 1]);
}

每当用户查询 N 时，我都会简单地输出 mx[N]。这个解决方案似乎是正确的。但是，对于较大的输入，它超过了时间限制(1 秒)。最大N为1,000,000，但用户可以查询1,000,000个不同的N值。以上代码是预处理代码，只运行一次。

上面代码的复杂度是 N + N/2 + N/3 + ... + 1，我想大概是 N Log N。如何提高这段代码的复杂度？

感谢您的帮助。

Answer 1

这道题的答案是:Highly Abundant Number
您可以从这里获取序列:A002093

实际上，我检查了10^10以下的所有高丰度数都是41-smooth数，而10^13以下是61-smooth数。
N-光滑数可以分解N以下的素数。
您可以像这个算法一样搜索 n-smooth 数(例如 47-smooth number below 10^16):

vector<int> p = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 };
vector<long long> s = { 1 }; long long lim = 10000000000000000;
for (int i = 0; i < p.size(); i++) {
    vector<long long> w;
    for (long long j : s) {
        long long mul = j;
        for (; mul <= lim; mul *= p[i]) w.push_back(mul);
    }
    s = w;
}

您可以在 O(log N + log X) 中分解 N 平滑数 X，因此您可以计算 divisor function对于 O(log N + log X)。

我给出了我的代码的结果，例如，我在 3.5 秒内使用 1GB 内存计算了所有 61 个小于 10^13 的平滑数。