[LGR-068]传染病研究

这道题做法很常规，考场上rush失败了QwQ

我们设 \(d_{n,k}=\sum[d|n^k]\) 那么显然对于 \(n\) 唯一分解后，\(d_{n,k}=\prod_{i=1}^n(kc_i+1)\)，\(c_i\) 质因数的质数 那么我们最后要求的答案必定为 \(k\) 的多项式，且多项式的次数不超过 \(8\)，因为 \(2\times3\times5\times7\times11\times13\times17\times19\times23>1\times10^7\)

所以我们取 \(k\in[0,8]\) 的值，其余值用拉格朗日插值插出来即可，对于前者，我们可以记录 \(d_{n,k}\) 的值和最小质因数的指数用线筛来维护，对于后者，可以 \(O(64logP)\) 也可以 \(O(8)\)

常数很大

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 1e7+5, P = 998244353;
int t, n, k, py[N][9], d[N], vis[N], p[N], num[N];
void solve(int n, int k)
{
    int tot = 0; py[1][k] = d[1] = 1;
    for(int i = 2; i <= n; ++i)
    {
        if(!vis[i]) p[++tot] = i, d[i]= k+1, num[i] = k;
        for(int j = 1; j <= tot&&i*p[j] <= n; ++j)
        {
            vis[i*p[j]] = 1;
            if(i%p[j] == 0) d[i*p[j]] = d[i]/(num[i]+1)*(num[i]+k+1), num[i*p[j]] = num[i]+k, j = tot;
            else d[i*p[j]] = d[i]*d[p[j]], num[i*p[j]] = k;
        }
        py[i][k] = (py[i-1][k]+d[i])%P, vis[i] = 0;
    }
}
int64 inv(int i) { return i == 1?1:P-(P/i)*inv(P%i)%P; }
int lagrange(int n, int *y, int xi) 
{
    int ans = 0;
    for (int i = 0; i <= n; ++i) 
    {
        int s1 = 1, s2 = 1;
        for (int j = 0; j <= n; ++j)
            if (i != j) 
            {
                s1 = 1ll*s1*(xi-j)%P;
                s2 = 1ll*s2*(i-j)%P;
            }
        ans = (1ll*ans+1ll*y[i]*s1%P*inv(s2)%P)%P;
    }
    return (ans+P)%P;
}
int main()
{
    n = 1e7;
    for(int i = 1; i <= n; ++i) py[i][0] = i;
    for(int i = 1; i <= 8; ++i) solve(n, i);
    t = read();
    while(t--)
    {
        n = read(), k = read();
        printf("%d\n", lagrange(8, py[n], k));
    }
    return 0;
}