题目：牛牛的数论

题解

令

令，注意这里的除法是狄利克雷卷积。

即

那么

发现一些性质：

根据积性函数的性质:

设，那么只要有一个那么

发现的一定能表示成，这样的数不超过个

我们暴力枚举每一个的，然后就只要算，这个可以用拉格朗日插值来求。

但每次都插值求一遍的话时间复杂度太高，我们把的值先预处理出来，的再插值。

时间复杂度:

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int mod=998244353;
const int N=1e6+5;
int n,m,k,cnt,ans,prim[N],vis[N],jc[N],inv[N],G[N],y[N],f[N][40];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
int kuai(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        b=b/2;
        a=a*a%mod;
    }
    return res;
}
void work(int n)
{
    jc[0]=jc[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=n;i++)jc[i]=jc[i-1]*i%mod;
    for(int i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=2;i<=n;i++)inv[i]=inv[i]*inv[i-1]%mod;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])prim[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            if(i*prim[j]>n)break;
            vis[i*prim[j]]=1;
            if(i%prim[j]==0)break;
        }
    }
}
int Cha(int n)
{
    if(n<=m)return y[n];
    int pre=1,res=0;
    for(int i=0;i<=k+1;i++)pre=pre*((n-i)%mod)%mod;
    for(int i=0;i<=k+1;i++)
    {
        int x=pre*kuai((n-i)%mod,mod-2)%mod*y[i]%mod;
        x=x*inv[i]%mod*inv[k+1-i]%mod;
        if((k+1-i)&1)x=mod-x;
        res=(res+x)%mod;
    }
    return res;
}
void dfs(int x,int val,int H)
{
    if(x>cnt||val>n/prim[x]/prim[x])
    {
        ans=(ans+H*Cha(n/val)%mod)%mod;
        return;
    }
    dfs(x+1,val,H);
    val=val*prim[x]*prim[x];
    for(int i=2;val<=n;val=val*prim[x],i++)
        dfs(x+1,val,H*f[x][i]%mod);
}
signed main()
{
    m=1e6;
    work(m);
    n=read();k=read();
    for(int i=0;i<=m;i++)G[i]=kuai(i,k);
    y[0]=G[0];
    for(int i=1;i<=m;i++)y[i]=(y[i-1]+G[i])%mod;
    for(int i=1;i<=cnt;i++)
    {
        int x=G[prim[i]];
        f[i][0]=1;
        f[i][1]=0;
        int t=1,lim=0;
        while(t*prim[i]<=n)
        {
            t=t*prim[i];
            lim++;
        }
        for(int j=2;j<=lim;j++)
        {
            f[i][j]=x;
            for(int p=0;p<j;p++)
                f[i][j]=(f[i][j]-f[i][p]*kuai(prim[i],k*(j-p))%mod+mod)%mod;
        }
    }
    dfs(1,1,1);
    cout<<ans;
    return 0;
}
/*
1000000000000 1000
*/