自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

搬运于2025-08-24 22:25:08，当前版本为作者最后更新于2022-01-10 19:57:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

$$\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;
}