bzoj 4916: 神犇和蒟蒻
给你正整数 ,求的值。
首先,第一行是搞笑的,因为 都有 ,所以第一行的值为 。
然后看第二行。知道 。设 ,则有
设根据 杜教筛的套路式,有即
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<map>
#define reg register
typedef long long ll;
const int MAXN=500;
const int MOD=1000000007;
ll n;
int len=0;
int p[MAXN+10];
bool vis[MAXN+10];
int phi[MAXN+10];
ll S_phi[MAXN+10];
ll inv6;
std::map<ll,ll>mp;
ll pow(ll x,int y){
if(!y) return 1;
ll c=pow(x,y/2)%MOD;
if(y&1) return (c*c)%MOD*x%MOD;
return (c*c)%MOD;
}
void init(){
memset(vis,1,sizeof(vis));phi[1]=1;
for(reg int i=2;i<=MAXN;++i){
if(vis[i]){
p[++len]=i;
phi[i]=i-1;
}
for(reg int j=1;i*p[j]<=MAXN&&j<=len;++j){
vis[i*p[j]]=0;
if(i%p[j])
phi[i*p[j]]=phi[i]*(p[j]-1);
else{
phi[i*p[j]]=phi[i]*p[j];
break;
}
}
}
S_phi[0]=0;
for(reg int i=1;i<=MAXN;++i){
phi[i]%=MOD;
S_phi[i]=(S_phi[i-1]+(ll)i*phi[i]%MOD)%MOD;
}
inv6=pow(6,MOD-2);
}
ll F(ll x){
return (ll)x*(x+1)%MOD*(x+x+1)%MOD*inv6%MOD;
}
ll C(ll l,ll r){
return (l+r)*(r-l+1)/2%MOD;
}
ll S(ll x){
if(x<MAXN) return S_phi[x];
if(mp[x]) return mp[x];
ll sum=0;
for(reg ll l=2,r;l<=x;l=r+1){
r=x/(x/l);
sum=(sum+S(x/l)*C(l,r)%MOD)%MOD;
}
return mp[x]=((F(x)-sum+MOD)%MOD);
}
int main(){
init();
scanf("%lld",&n);
printf("1\n%lld",S(n));
}
优质内容筛选与推荐>>