论自然求和在 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 上是最短的，欢迎大家继续优化码长。 ```cpp #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; } ```