莫比乌斯函数前缀和
const int __=5e6; //n^(2/3)项
bool pri[__+5];
int mu[__+5],num[__+5];
ll sum[__+5];
void mobius()
{
mu[1]=sum[1]=1;
pri[1]=true;
for(int i=2;i<=__;i++)
{
if(!pri[i])
{
num[++num[0]]=i;
mu[i]=-1;
}
for(int j=1;j<=num[0] && i*num[j]<=__;++j)
{
int &p=num[j];
pri[i*p]=true;
if(!(i%p)){mu[i*p]=0;break;}
mu[i*p]=-mu[i];
}
sum[i]=sum[i-1]+mu[i];
}
}
unordered_map<ll,ll>dp;
ll cal(ll x)
{
if(x<=__)return sum[x];
if(dp[x])return dp[x];
ll res=1;
for(ll l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
res-=(r-l+1)*cal(x/l);
}
return dp[x]=res;
}
欧拉函数前缀和(取模)
const int __=5e6;
const int mod=1e9+7;
const int inv2=(mod+1)/2;
ll md(ll x)
{
if(x<=-mod || x>=mod)
x%=mod;
if(x<0)x+=mod;
return x;
}
int phi[__+5],num[__+5];
ll sum[__+5];
void euler()
{
phi[1]=sum[1]=1;
for(int i=2;i<=__;i++)
{
if(!phi[i])
{
num[++num[0]]=i;
phi[i]=i-1;
}
for(int j=1;j<=num[0] && i*num[j]<=__;++j)
{
int &p=num[j];
if(!(i%p))
{
phi[i*p]=phi[i]*p;
break;
}
phi[i*p]=phi[i]*(p-1);
}
sum[i]=sum[i-1]+phi[i];
if(sum[i]>=mod)sum[i]-=mod;
}
}
unordered_map<ll,ll>dp;
ll cal(ll x)
{
if(x<=__)return sum[x];
if(dp[x])return dp[x];
ll res=md(md((md(x)+1ll)*md(x))*inv2);
for(ll l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
res=md(res-md(md(r-l+1)*cal(x/l)));
}
return dp[x]=res;
}
