莫比乌斯反演的一些简单应用#1
AFO_WR_Eternity
2019-06-08 10:37:27
莫比乌斯反演的式子我们在之前已经推导出来了为：
$f(n)=\sum_{d|n}g(d),g(n)=\sum_{d|n}f(d)\times\mu(\frac n d)$
具体的推导过程可以参考我之前的一篇[博客](https://www.cnblogs.com/WR-Eternity/p/10939746.html)。
而我们在推导莫比乌斯反演这个式子之前，曾得到另外一个同样也很重要的式子：
$\sum_{d|n}\mu(d)=[n=1]$
也就是 $\mu*1=\epsilon$ 。
这个式子有啥用呢？
我们把它稍稍转换一下，令 $n=gcd(i,j)$，这样的话，式子就变成了：
$\sum_{d|gcd(i,j)}\mu(d)=[gcd(i,j)=1]$
而我们可以通过交换 $\Sigma$ 的位置来实现对一些类似 $gcd(i,j)=1$ 式子的求解。
# 例1:
求：$\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=1]$ 。
这个就是我上面说的式子的一个具体应用啦，有了上面的式子，这个问题还是很简单的啦。
$\ \ \ \ \sum_{i=1}^n\sum_{j=1}^{m}[gcd(i,j)=1]$
$=\sum_{i=1}^n\sum_{i=1}^m\sum_{d|gcd(i,j)}\mu(d)$
$=\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac n d\rfloor}\sum_{j=1}^{\lfloor\frac m d\rfloor}$
$=\sum_{d=1}^n\mu(d)\times\lfloor\frac n d\rfloor\times\lfloor\frac m d\rfloor$
然后就可以在$O(\sqrt{n})$ 的时间内求解了。
因为是例1，所以还是贴个代码，当个示范：
```cpp
#include<bits/stdc++.h>
#define ll long long
const int N=10000000;
int mu[N+5],vis[N+5],sum[N+5],p[N+5];
ll ans;
int n,m,q;
using namespace std;
void sieve(){
mu[1]=vis[1]=1;
for(int i=2;i<=N;i++){
if (!vis[i]) p[++p[0]]=i,mu[i]=-1;
for (int j=1;j<=p[0]&&i*p[j]<=N;j++){
vis[i*p[j]]=1;
if (i%p[j]==0){
mu[i*p[j]]=0;
break;
}
mu[i*p[j]]=-mu[i];
}
}
for (int i=1;i<=N;i++)
mu[i]+=mu[i-1];
}
int main(){
sieve();
scanf("%d",&q);
while (q--){
scanf("%d%d",&n,&m);
if (n>m) swap(n,m);
ans=0;
for (int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
ans+=1ll*(mu[r]-mu[l-1])*(n/l)*(m/l);
}
printf("%lld\n",ans);
}
return 0;
}
```
# 例2：
求：$\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=k]$ 。
其实这里只需要一个很简单的转化：
$\ \ \ \ \sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=k]$
$=\sum_{i=1}^{\lfloor\frac n k\rfloor}\sum_{j=1}^{\lfloor\frac m k\rfloor}[gcd(i,j)=1]$
然后就和上面一样啦。
# 例3：
求：$\sum_{i=1}^n\sum_{j=1}^mi\times j\times[gcd(i,j)=k]$
这个和上面其实也没有什么大差别，这里的$i,j$其实只是一个副产品，只要我们移$\Sigma$的时候不要忘记对$i,j$项产生的影响即可。
$\ \ \ \ \sum_{i=1}^n\sum_{j=1}^mi\times j\times[gcd(i,j)=k]$
$=\sum_{i=1}^{\lfloor\frac n k\rfloor}\sum_{j=1}^{\lfloor\frac m k\rfloor}i\times j\times k^2\times[gcd(i,j)=1]$
$=k^2\times\sum_{d=1}^{\lfloor\frac n k\rfloor}\mu(d)\times\sum_{i=1}^{\lfloor\frac n {kd}\rfloor}i\times\sum_{j=1}^{\lfloor\frac m {kd}\rfloor}j$
令$sum[n]=\sum_{i=1}^ni$ 。
$=k^2\times\sum_{d=1}^{\lfloor\frac n k\rfloor}d^2\times\mu(d)\times sum[\lfloor\frac n {kd}\rfloor]\times sum[\lfloor\frac m {kd}\rfloor]$
$O(\sqrt{n})$ 求解即可。
好了，先就这么多吧，剩下还有很多，毕竟莫比乌斯反演博大精深，以后再写了。