@[Gax_c](/space/show?uid=13494)
%%%
by Jeanne_Alter @ 2018-12-09 19:03:35
@[HermioneGranger](/space/show?uid=95405)
大佬求教
by Gax_c @ 2018-12-09 19:10:55
@[Gax_c](/space/show?uid=13494) %%%，反演dalao
by yzhang @ 2018-12-09 19:14:41
```
#include<bits/stdc++.h>
using namespace std;
int mu[100004],tot,T,p[100004],vis[100004],sum[100004],n,m;
inline void init(){
int nx=100000;mu[1]=1;
for (register int i=2;i<=nx;i++){
if (!vis[i]) p[++tot]=i,mu[i]=-1;
for (register int j=1;j<=tot&&i*p[j]<=nx;j++){
if (i*p[j]>nx) continue;
vis[i*p[j]]=1;
if((i%p[j])==0){
mu[i*p[j]]=0;
break;
}
mu[i*p[j]]=-mu[i];
}
}
for (register int i=1;i<=nx;i++){
sum[i]=sum[i-1]+mu[i];
}
}
inline long long Fun(int a,int b,int d){
long long ans=0;
for (int l=1,r;l<=min(a,b);l=r+1){
r=min(a/(a/l),b/(b/l));
ans+=(long long)(sum[r]-sum[l-1])*(a/(l*d))*(b/(l*d));
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
init();
long long ans=0;
for (register int i=1;i<=min(n,m);i++){
ans+=Fun(n,m,i)*i;
}
cout<<2*ans-n*m;
}```
我一开始直接mofan的，被卡成九十，过不去
by Fading @ 2018-12-09 19:19:51
@[Fading](/space/show?uid=20309)
为什么我会WA啊
by Gax_c @ 2018-12-09 19:23:50
我的莫反AC了?
by command_block @ 2018-12-16 11:45:19
能吧，我的式子推出来没有phi
by 南方不败 @ 2019-04-28 15:40:49
如果式子推出来没有 $\boldsymbol \varphi(n)$ ，那肯定就有 $\displaystyle \sum_{d\mid n} \boldsymbol \mu(d){n\over d}$ 之类的
实际上会发现它是积性函数，就会令 $\displaystyle \boldsymbol f(n)=\sum_{d\mid n}\boldsymbol \mu(d){n\over d}$
然后推 $\boldsymbol f(n)$ 的线筛公式，接着就会发现其实 $\boldsymbol f=\boldsymbol \varphi$ 。。。。。。
---
因为其实 $\displaystyle \sum_{d\mid n} \boldsymbol \mu(d){n\over d}=\sum_{d\mid n}\boldsymbol \mu(d)\boldsymbol {id}({n\over d})$
如果懂得迪利克雷卷积就是 $(\boldsymbol \mu*\boldsymbol {id})(n)$
而 $\boldsymbol \varphi*\boldsymbol I=\boldsymbol {id}$
两边同时卷一个 $\boldsymbol \mu$
$\boldsymbol \varphi*\boldsymbol I*\boldsymbol \mu=\boldsymbol {id}*\boldsymbol \mu$
即 $\boldsymbol {id}*\boldsymbol \mu=\boldsymbol \varphi$
by JustinRochester @ 2019-08-26 12:22:32