论自然求和在 codegolf 中的应用

· · 题解

另一篇题解已经指出，答案序列就是

\left(\sum_{n\ge 1} \sigma_0(n) x^n\right)^2

考虑 \sigma_0(n) 是 ab=n 的解数，不妨设 a\le b，可以写出

\sum_{n\ge 1}\sigma_0(n)x^n = \sum_{h\ge 1} x^{h^2} \frac{1+x^h}{1-x^h}

由于最低次项为 h^2，我们只需要考虑 h\le \sqrt n 的部分，因此我们可以在 O(n^{3/2}) 的时间内计算出 f(x) \cdot \sum_{n\ge 1} \sigma_0(n) x^n。

综上，我们可以在 O(n^{3/2}) 的时间完成预处理。虽然比 FFT 慢，但是它的优点是短！

正常缩进的本代码目前在 CF 上是最短的，欢迎大家继续优化码长。

#include <bits/stdc++.h>

using namespace std;

const int N = 500000;

int f[N + 5], g[N + 5], h[N + 5];

int main() {
    for (int i = 1; i <= N; ++i)
        for (int j = i; j <= N; j += i)
            ++f[j];
    for (int i = 1, t; (t = i * i) <= N; ++i) {
        memcpy(g, f, sizeof(g));
        for (int j = N - t; j >= i; --j) g[j] += g[j - i];
        for (int j = i; j <= N - t; ++j) g[j] += g[j - i];
        for (int j = 0; j <= N - t; ++j) h[j + t] += g[j];
    }
    int Q; cin >> Q;
    while (Q--) {
        int l, r; cin >> l >> r;
        int pos = max_element(h + l, h + r + 1) - h;
        cout << pos << ' ' << h[pos] << '\n';
    }

    return 0;
}