题解 P6060 【[加油武汉]传染病研究】

小粉兔 · 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;
}