10AC+1WA

记录

#include<bits/stdc++.h>
using namespace std;
inline long long read(){
	long long x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x;
}
void write(int x){
	static int sta[20];
	int top=0;
	do{
		sta[top++]=x%10,x/=10;
	}while(x);
	while(top) putchar(sta[--top]+48);
}
long long n;
const int mod=998244353;
int m,k,f[10000010],g[10000010],h[10000010],mu[10000010],prime[1000010],tot;
int ss[10000010],cz[110],phi[10000010],xian[1145],zong[1145],temp1[1145],temp[1145];
bool check[10000010];
map<long long,int>mp,mp2;
inline int pi(long long x){
	if(x<=10000000) return phi[x];
	if(mp[x]) return mp[x];
	int temp=x%mod;
	int ret=1ll*temp*(temp+1)/2%mod;
	for(long long i=2,j;i<=x;i=j+1){
		j=x/(x/i);
		ret=(ret-(j-i+1)%mod*pi(x/i)%mod+mod)%mod;
	}
	return mp[x]=ret;
}
inline int ksm(int x,int y){
	int ret=1;
	while(y){
		if(y&1) ret=1ll*ret*x%mod;
		y>>=1;
		x=1ll*x*x%mod;
	}
	return ret;
}
void init(){
	f[1]=m;
	g[1]=1;
	mu[1]=1;
	ss[1]=1;
	phi[1]=1;
	for(int i=2;i<=10000000;i++){
		if(!check[i]){
			prime[++tot]=i;
			g[i]=1;
			h[i]=1;
			mu[i]=-1;
			ss[i]=ksm(i,k);
			phi[i]=i-1;
		}
		for(int j=1;j<=tot&&i*prime[j]<=10000000;j++){
			check[i*prime[j]]=1;
			ss[i*prime[j]]=1ll*ss[i]*ss[prime[j]]%mod;
			if(i%prime[j]==0){
				h[i*prime[j]]=h[i]+1;
				g[i*prime[j]]=max(h[i]+1,g[i]);
				mu[i*prime[j]]=0;
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			h[i*prime[j]]=1;
			g[i*prime[j]]=g[i];
			mu[i*prime[j]]=-mu[i];
			phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
		f[i]=1ll*max(m-g[i]+1,0)*ss[i]%mod;
	}
	for(int i=1;i<=10000000;i++) f[i]=(f[i]+f[i-1])%mod,phi[i]=(phi[i]+phi[i-1])%mod;
	for(int i=2;i<=k+2;i++) xian[i]=(xian[i-1]+ss[i-1])%mod;
	zong[0]=1;
	for(int i=1;i<=k+2;i++){
		for(int j=0;j<i;j++) temp1[j]=zong[j];
		for(int j=1;j<=i;j++) zong[j]=temp1[j-1];
		zong[0]=0;
		for(int j=0;j<i;j++) zong[j]=(zong[j]-1ll*(i-1)*temp1[j]%mod+mod)%mod;
	}
	for(int i=1;i<=k+2;i++){
		int tmp=1;
		for(int j=1;j<=k+2;j++){
			if(j!=i) tmp=1ll*tmp*(i-j+mod)%mod;
		}
		tmp=ksm(tmp,mod-2);
		tmp=1ll*tmp*xian[i]%mod;
		for(int j=k+2;j>=0;j--) temp[j]=zong[j];
		for(int j=k+2;j>=1;j--){
			temp1[j-1]=temp[j];
			temp[j-1]=(temp[j-1]+1ll*(i-1)*temp[j])%mod;
		}
		for(int j=0;j<k+2;j++) cz[j]=(cz[j]+1ll*temp1[j]*tmp)%mod;
	}
	//for(int i=0;i<=k+1;i++) cout<<cz[i]<<endl;
}
inline int s(long long x){
	if(mp2[x]) return mp2[x];
	x%=mod;
	int ret=0;
	for(int i=k+1;i>=0;i--) ret=(x*ret+cz[i])%mod;
	return mp2[x]=ret;
}
int ff(long long x){
	if(x<=10000000) return f[x];
	int ret=1ll*m*s(x)%mod;
	for(int i=2;1ll*i*i<=x;i++){
		if(mu[i]){
			long long j=x/i/i;
			int xxx=1ll*ss[i]*ss[i]%mod;
			for(int u=2;u<=m&&j;++u,j/=i){
				ret=(ret+1ll*mu[i]*xxx%mod*s(j)%mod+mod)%mod;
				//if(x==10010010&&i<=100) printf("mu[%d]=%d,xxx=%d,s(%lld)=%d,ret=%d\n",i,mu[i],xxx,j,s(j),ret);
				xxx=1ll*xxx*ss[i]%mod;
			}
		}
	}
	return ret;
}
int main(){
	n=read();
	m=read();
	k=read();
	assert(m==1);
	init();
	int ans=0;
	int prev=0;
	for(long long i=1,j;i<=n;i=j+1){
		j=n/(n/i);
		int temp=ff(j);
		ans=(ans+1ll*(temp-prev+mod)*(2*pi(n/i)-1)%mod)%mod;
		prev=temp;
	}
	write(ans);
	return 0;
}