Time Limits: 1000 ms Memory Limits: 30760 KB

Description

Input

Output

Sample Input

10 3

Sample Output

714

Data Constraint

analysis

这。。。空间有点醉

杜教筛的常用套路
设$f[n]=\sum_{i=1}^n i^m\mu(i)$
首先有$\sum_{i=1}^n i^m\sum_{d|i}\mu(d)=1$

移项得$f(n)=1-\sum_{i=2}^n i^mf(\lfloor\frac ni\rfloor)$

于是可以套杜教筛，这需要自然数幂和，拉格朗日插值法

能过？想太多，直接拉格朗日肯定过不了，再加上卡空间。。。

杜教筛只用预处理1e6个
在预处理5e6个自然数幂和，其余的自然数幂和也只不过$n/5e6$个，预处理拉格朗日插值法即可。

注意拉格朗日要m+2个量

时间复杂度$O(n^{\frac 23}+\frac{nm}{5*10^6})$，空间卡过

#include
#include
#define N 1000000
#define ll long long
#define lim 10007
#define mo 998244353using namespace std;int mu[N+1],mp[N*5+1],pr[100100],f[N+1],hash[lim][2],n,m,init[201];
int tmp[100010],pre[100010],suf[100010],ifr[100010];
bool bz[N+1];int qpow(int a,int i){int r=1;for(;i;i>>=1,a=(ll)a*(ll)a%mo)if(i&1)r=(ll)r*(ll)a%mo;return r;
}int get(int x){int y=x%lim;while(hash[y][0] && hash[y][0]!=x)y=(y+1)%lim;return y;
}int mpow(int x){if(x<=5*N)return mp[x];return init[n/x];
}int query(int n){if(n<=N)return f[n];int x=get(n);if(hash[x][0]==n)return hash[x][1];hash[x][0]=n;int ans=1;for(int i=2,j,las=1;i<=n;i=j+1){j=n/(n/i);int k=mpow(j);ans=((ll)ans+(ll)mo-((ll)mo+(ll)k-(ll)las)%mo*query(n/i)%mo)%mo;las=k;}hash[x][1]=ans;return ans;
}int main(){scanf("%d %d",&n,&m);f[1]=1;mp[1]=1;for(int i=2;i<=N*5;i++){if(mp[i]==0)mp[i]=qpow(i,m);if(i<=N){if(!bz[i])pr[++pr[0]]=i,mu[i]=mo-1;f[i]=((ll)f[i-1]+(ll)mu[i]*(ll)mp[i])%mo;}for(int j=1;j<=pr[0] && i*pr[j]<=5*N;j++){if(i*pr[j]<=N)bz[i*pr[j]]=1,mu[i*pr[j]]=mo-mu[i];mp[i*pr[j]]=(ll)mp[i]*(ll)mp[pr[j]]%mo;if(i%pr[j]==0){if(i*pr[j]<=N)mu[i*pr[j]]=0;break;}}}for(int i=2;i<=5*N;i++)mp[i]=(mp[i]+mp[i-1])%mo;ifr[0]=1;ifr[m+1]=1;for(int i=2;i<=m+1;i++)ifr[m+1]=(ll)ifr[m+1]*(ll)i%mo;ifr[m+1]=qpow(ifr[m+1],mo-2);for(int i=m;i;i--)ifr[i]=(ll)ifr[i+1]*(ll)(i+1)%mo;for(int j=1;n/j>N*5;j++){int x=n/j;init[j]=0;for(int i=0;i<=m+1;i++)tmp[i]=x-i;pre[0]=tmp[0];suf[m+1]=tmp[m+1];for(int i=1;i<=m+1;i++)pre[i]=(ll)pre[i-1]*(ll)tmp[i]%mo;for(int i=m;i>=0;i--)suf[i]=(ll)suf[i+1]*(ll)tmp[i]%mo;for(int i=0;i<=m+1;i++)init[j]=((ll)init[j]+(ll)mp[i]*(ll)(i?pre[i-1]:1)%mo*(ll)((i<1+m)?suf[i+1]:1)%mo*(ll)ifr[i]%mo*(ll)ifr[m+1-i]%mo*((((m+1-i)&1)==0)?1:mo-1))%mo;}printf("%d",query(n));return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！