自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 22:17:00，当前版本为作者最后更新于2020-02-10 21:33:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

为了刷点社区贡献我来写题解。

啊 $D$ 其实就是 $\sigma_0$ 是吧，就是约数个数函数。

我们知道 $\sigma_0 (n)$ 的求法：把 $n$ 质因数分解，得到 $p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_c^{\alpha_c}$ 的话，则 $\sigma_0 (n) = \prod\limits_{i=1}^{c} (\alpha_i + 1)$。

然后我们发现，$n^k$ 的质因数分解就是 $p_1^{k \cdot \alpha_1} p_2^{k \cdot \alpha_2} \cdots p_c^{k \cdot \alpha_c}$。

所以 $\sigma_0 (n^k) = \prod\limits_{i=1}^{c} (k \cdot \alpha_i + 1)$。

不妨举个例子，比如 $360 = 2^3 \cdot 3^2 \cdot 5$，则 $\sigma_0 ({360}^k) = (3k + 1) (2k + 1) (k + 1)$。

展开一下：$\sigma_0 ({360}^k) = 1 + 6 k + 11 k^2 + 6 k^3$。

啊，原来是一个关于 $k$ 的 $3$ 次多项式啊！

为啥是 $3$ 次？因为 $360$ 恰好就有 $3$ 个质因子：$2, 3, 5$。

也就是说，有多少个质因子就是关于 $k$ 的多少次多项式吧。

然而 ${10}^7$ 之内的，质因子最多的数，也不过 $8$ 个（$9699690 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19$）。

所以说啊，对于任何 $n \le {10}^7$，$\sigma_0 (n^k)$ 顶多就是关于 $k$ 的 $8$ 次多项式而已。

众所周知，无论多少个 $8$ 次多项式，加起来也还是 $8$ 次多项式。

如果我们已经得到了，每个 $n$ 对应的多项式，就可以 $\mathcal O (8)$ 算答案了。

所以写个线筛就可以求多项式的系数了，然后做一下前缀和，就做完了。

代码如下，时间复杂度为 $\mathcal O (n \cdot 8 + T \cdot 8)$：

#include <cstdio>
#include <cstring>

typedef long long LL;
const int Mod = 998244353;
const int MN = 10000007, MP = 664580;

bool ip[MN];
int p[MP], pc;
int lpf[MN], lpfc[MN], dlpf[MN];
int poly[MN][9];
void Sieve(int N) {
	poly[1][0] = 1;
	for (int i = 2; i <= N; ++i) {
		if (!ip[i]) p[++pc] = i, lpf[i] = i, lpfc[i] = 1, dlpf[i] = 1, poly[i][0] = poly[i][1] = 1;
		for (int j = 1, k; j <= pc; ++j) {
			if ((k = p[j] * i) > N) break;
			ip[k] = 1;
			lpf[k] = j;
			if (i % p[j]) lpfc[k] = 1, dlpf[k] = i;
			else lpfc[k] = lpfc[i] + 1, dlpf[k] = dlpf[i];
			memcpy(poly[k], poly[dlpf[k]], 36);
			for (int z = 8; z >= 1; --z) poly[k][z] = (poly[k][z] + (LL)lpfc[k] * poly[k][z - 1]) % Mod;
			if (i % p[j] == 0) break;
		}
	}
	for (int i = 1; i <= N; ++i)
		for (int j = 0; j <= 8; ++j)
			poly[i][j] -= (poly[i][j] += poly[i - 1][j]) >= Mod ? Mod : 0;
}

int main() {
	Sieve(10000000);
	int T;
	scanf("%d", &T);
	while (T--) {
		int N, K;
		scanf("%d%d", &N, &K);
		int Ans = 0;
		for (int i = 8; i >= 0; --i)
			Ans = ((LL)Ans * K + poly[N][i]) % Mod;
		printf("%d\n", Ans);
	}
	return 0;
}