Count

題目鏈接：點這里

題目意思：令f(x)表示<=x的正整數中與x互質的數的平均數*2，求sigma(f(i)^k),L<=i<=R

Solution:

首先，我們定義\(S(x)=\sum_{gcd(a,x)=1}a\)，因為gcd(a,x)=1，所以對于任意a，滿足gcd(x-a,x)=1

我們知道滿足條件的a只有\(\phi(x)\)個，所以可以得到\(S(x)=\frac{\phi(x)x}{2}\)

我們要求的\(f(x)=2\frac{S(x)}{\phi(x)}\)，可以得到\(f(x)=x\)，于是可以得到我們要求的數為\(\sum_{i=L}^R i^k\)

于是我們可以直接用拉格朗日插值來求

Code:

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int N=1e6+1;
int l,r,k,u,ans,pro,f[N],fac[N]={1};
int quickpow(int x,int y){int re=1;while(y){if(y&1) re=re*x%mod;x=x*x%mod;y>>=1;}return re%mod;
}
void prepare(){for(int i=1;i<=k+2;i++)f[i]=(f[i-1]+quickpow(i,k))%mod;for(int i=1;i<=k+2;i++)fac[i]=fac[i-1]*i%mod;
}
int Lagrange(int n){pro=1,ans=0;for(int i=1;i<=k+2;i++)pro=pro*(n-i)%mod;for(int i=1;i<=k+2;i++){int inv1=quickpow(n-i,mod-2);int inv2=quickpow((fac[i-1]%mod*fac[k+2-i])%mod,mod-2);int sign=(k+2-i)&1?-1:1;ans=(ans+sign*inv1*inv2%mod*f[i]%mod*pro%mod)%mod;}return (ans+mod)%mod;
}
int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;
}
signed main(){l=read(),r=read(),k=read();prepare();u=(l<=k+3)?f[l-1]:Lagrange(l-1);int now;now=(r>k+2)?Lagrange(r):f[r];printf("%lld\n",(now-u+mod)%mod);return 0;
}