Luogu6060 [加油武汉] 传染病研究

发表于 分类于 ， ， 阅读次数：

题意：给出 ，求

多组询问，，，时限 。

对于 有

可以发现 是一个关于 的多项式，且次数比较低，只有 。

使用线性筛预处理多项式，并求前缀和。询问只需代入即可。复杂度为 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>

const int MaxN = 1e7+5, mod = 998244353;
int p[MaxN/8], totP, F[MaxN][9];

void sieve(int n) {
    F[1][0] = 1;
    for (int i=2; i<=n; i++) {
        if (!F[i][0]) {
            p[++totP] = i;
            F[i][0] = F[i][1] =1;
        }
        for (int j=1; j<=totP; j++){
            int t = i*p[j];
            if (t>n) break;
            F[t][0] = 1;
            if (i%p[j]==0) {
                int u=i, c=1;
                while(u%p[j]==0) {
                    u /= p[j];
                    c++;
                }
                for (int k=1; k<=8; k++)
                    F[t][k] = (F[u][k]+1ll*c*F[u][k-1])%mod;
                break;
            }
            for (int k=1; k<=8; k++)
                F[t][k] = (F[i][k]+F[i][k-1]) %mod;
        }
    }
    for (int i=1;i<=n;i++)
        for (int j=0;j<9;j++)
            F[i][j] = (F[i][j]+F[i-1][j]) %mod;
}

int calc(int n, int k) {
    int ans=0, buf=1;
    for (int i=0; i<9; i++){
        ans = (ans+1ll*F[n][i]*buf) %mod;
        buf = 1ll*buf*k %mod;
    }
   return ans;
}

int main() {
    sieve(1e7);
    
    int T;
    scanf("%d", &T);
    
    while(T--) {
        int N, K;
        scanf("%d%d", &N, &K);
        printf("%d\n", calc(N, K));
    }
    
    return 0;
}