bzoj 4176 Lucas的数论 题解【莫比乌斯反演】【杜教筛】

Description

$$\sum_{i=1}^n\sum_{j=1}^nf(ij)$$

Sample Input

2


Sample Output

8


题解：

\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^nd(ij)\\ =&\sum_{i=1}^n\sum_{j=1}^n\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1] \end{aligned}
（题面中的 $f$ 已转成 $d$）令
f(k)=\sum_{i=1}^n\sum_{j=1}^n\sum_{x|i}\sum_{y|j}[\gcd(x,y)=k]\\ \begin{aligned} g(k)&=\sum_{k|d}f(d)\\ &=\sum_{i=1}^n\sum_{j=1}^n\sum_{x|i}\sum_{y|j}[k|\gcd(x,y)]\\ &=\sum_{i=1}^\left\lfloor\frac nk\right\rfloor\sum_{j=1}^\left\lfloor\frac nk\right\rfloor\sum_{x|i}\sum_{y|j}[1|\gcd(x,y)]\\ &=\sum_{i=1}^\left\lfloor\frac nk\right\rfloor\sum_{j=1}^\left\lfloor\frac nk\right\rfloor d(i)d(j) \end{aligned} \\ \begin{aligned} f(k)&=\sum_{k|d}\mu\left(\frac dk\right)g(d)\\ &=\sum_{i=1}^\left\lfloor\frac nk\right\rfloor\mu(i)g(ki) \end{aligned}

$$\sum_{i=1}^n\mu(i)sumd^2\left(\left\lfloor\frac ni\right\rfloor\right)$$

//以下部分感谢 _rqy 的指导

\begin{aligned} sumd(k)&=\sum_{i=1}^k\sum_{j|i}1\\ &=\sum_{j=1}^k\sum_{j|i}1\\ &=\sum_{j=1}^k\left\lfloor\frac kj\right\rfloor \end{aligned}

Code：

#include<cstdio>
#include<cstring>
#define ll long long
#define p 1000000007
int mu[3000100],gmu[5000];
ll d[3000100],f[3000100],gd[5000];
bool is[3000100],usedmu[5000],usedd[5000];
int pri[3000100],cnt=0,n;
int calcmu(int x)
{
if(x<=3000000)
return mu[x];
int t=n/x;
if(usedmu[t])
return gmu[t];
usedmu[t]=1;
ll ans=1;
for(int i=2;i<=x;++i)
{
int nxt=x/(x/i);
ans=(ans-(ll)calcmu(x/i)*(nxt-i+1)%p+p)%p;
i=nxt;
}
return gmu[t]=ans;
}
int calcd(int x)
{
if(x<=3000000)
return d[x];
int t=n/x;
if(usedd[t])
return gd[t];
usedd[t]=1;
ll ans=0;
for(int i=1;i<=x;++i)
{
int nxt=x/(x/i);
ans=(ans+(ll)x/i*(nxt-i+1))%p;
i=nxt;
}
return gd[t]=ans;
}
int main()
{
is[0]=is[1]=1;
mu[1]=1;
d[1]=1;
for(int i=2;i<=3000000;++i)
{
if(!is[i])
{
pri[++cnt]=i;
mu[i]=-1;
f[i]=2;
d[i]=2;
}
for(int j=1;j<=cnt&&i*pri[j]<=3000000;++j)
{
is[i*pri[j]]=1;
if(i%pri[j])
{
mu[i*pri[j]]=-mu[i];
f[i*pri[j]]=2;
d[i*pri[j]]=2*d[i];
}
else
{
mu[i*pri[j]]=0;
f[i*pri[j]]=f[i]+1;
d[i*pri[j]]=d[i]/f[i]*f[i*pri[j]];
break;
}
}
d[i]=(d[i-1]+d[i])%p;
mu[i]=((mu[i-1]+mu[i])%p+p)%p;
}
scanf("%d",&n);
ll ans=0;
for(int i=1;i<=n;++i)
{
int nxt=n/(n/i);
ll k=calcd(n/i);
ans=(ans+k*k%p*(calcmu(nxt)-calcmu(i-1))%p+p)%p;
i=nxt;
}
printf("%lld\n",ans);
return 0;
}


Subscribe

/* */