莫比乌斯反演

数论

---

Prob 1：

给你 $n,m$，求$1\leq x\leq n,1\leq y\leq m$并且$gcd(x,y){\rm\ is\ prime}$的$(x,y)$的数目

思路一：直接利用常用公式进行变换

$$\sum_{p{\rm\ is\ prime}}\sum_{i=1}^N\sum_{j=1}^M[gcd(i,j)=p]$$
$$=\sum_p\sum_{i=1}^{\lfloor\frac{N}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{p}\rfloor}[gcd(i,j)=1]$$
$$=\sum_p\sum_{i=1}^{\lfloor\frac{N}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{p}\rfloor}\sum_{d\mid gcd(i,j)}\mu(d)$$
$$=\sum_p\sum_d\mu(d)\sum_{i=1}^{\lfloor\frac{N}{p}\rfloor}[d\mid i]\sum_{j=1}^{\lfloor\frac{M}{p}\rfloor}[d\mid j]$$
$$=\sum_p\sum_d\mu(d)\cdot \lfloor\frac{N}{p\cdot d}\rfloor\cdot\lfloor\frac{M}{p\cdot d}\rfloor$$
我们设 $T=p\cdot d$
$$ans=\sum_T\lfloor\frac{N}{T}\rfloor\cdot\lfloor\frac{M}{T}\rfloor\cdot\sum_{p\mid T \ \wedge\ p{\rm\ is\ prime}}\mu(\frac{T}{p})$$
我们设 $g(x)=\sum_{p\mid x \ \wedge\ p{\rm\ is\ prime}}\mu(\frac{x}{p})$
通过观察，我们觉得$g(x)$很像狄利克雷卷积。但是，很抱歉，它不是……
所以$g(x)$不是积性函数。不能用筛法啦！！！
真的不能用筛法了吗？
其实可以。
我们来推导$g(i\cdot p)(p{\rm\ is\ prime})$的性质：
$g(i\cdot p)=\sum_{d\mid i\cdot p}\mu(\frac{i\cdot p}{d})=\mu(i)+\sum_{d\mid i\cdot p \ \wedge\ d\neq p}\mu(\frac{i\cdot p}{d})$
$\because d,p{\rm\ is\ prime}$
$\therefore g(i\cdot p)=\mu(i)+\sum_{d\mid i}\mu(\frac{i\cdot p}{d})$
${\rm When\ \ }p\mid i,\ i\equiv k\cdot p,\ \mu(\frac{i\cdot p}{d})=\mu(\frac{k\cdot p^2}{d})=0,\ g(i\cdot p)=0$
${\rm When\ \ }p\nmid i,gcd(i,p)=1,\ \mu(\frac{i\cdot p}{d})=\mu(\frac{i}{d})\cdot\mu(p)=-\mu(\frac{i}{d}),g(i\cdot p)=\mu(i)-\sum_{d\mid i}\mu(\frac{i}{d})=\mu(i)-g(i)$
于是我们可以筛法“筛”出$g(x)$函数了。
剩下的就很简单了，不再赘述。

当然，我们的最终目的其实只是获得$\sum_{p\mid T}\mu(\frac{T}{p})$的前缀和，对吧？
既然如此，我们何不采取更为直接的方法呢？
直接暴力枚举质数，去更新这个质数的倍数的前缀和！
由$\ \lim_{n\rightarrow\infty}\sum_{i=1}^n\frac{1}{i}=\ln{n}+r$这个结论易知每个质数更新时是均摊$\Theta(\log{n})$的
而质数的个数恰好是$\Theta(\frac{n}{\log{n}})$的
所以这样暴力维护的效率是均摊$\Theta(N)$的。

思路二：莫比乌斯反演

既然是莫比乌斯反演啦，当然就要构造两个函数了。
$f(d)=\sum_{i=1}^N\sum_{j=1}^M[gcd(i,j)=d]$
$g(d)=\sum_{i=1}^N\sum_{j=1}^M[d\mid gcd(i,j)]$
二者之间的关系：
$g(x)=\sum_{d\mid x}f(d)$
根据莫比乌斯反演
$f(x)=\sum_{x\mid d}\mu(\frac{d}{x})g(d)$
很明显$g(x)=\lfloor\frac{N}{x}\rfloor\cdot\lfloor\frac{M}{x}\rfloor$
$f(x)=\sum_{x\mid d}\mu(\frac{d}{x})\cdot\lfloor\frac{N}{x}\rfloor\cdot\lfloor\frac{M}{x}\rfloor$
通过换元
$f(x)=\sum_d\mu(d)\cdot\lfloor\frac{N}{x\cdot d}\rfloor\cdot\lfloor\frac{M}{x\cdot d}\rfloor$
那么$ans=\sum_{p,{\rm p\ is\ prime}}f(p)$
剩下的不讲了，和思路一完全一样。不再赘述。

---

Prob 2：

多次询问，每次给你$\ a,b,c,d,k$，询问$\sum_{i=a}^b\sum_{j=c}^d[gcd(i,j)=k]$

有上下边界怎么办？
先不考虑边界限制！
我们考虑这个问题的简化版：
询问$\sum_{i=1}^N\sum_{j=1}^M[gcd(i,j)=k]$
这个很水吧？就是上面的$\ Prob\ 1$
那么加上边界怎么办？
考虑“容斥原理”
$f(a,b,c,d,k)=g(b,d,k)-g(a-1,d,k)-g(c-1,b,k)+g(a-1,c-1,k)$
问题解决。

容斥原理、莫比乌斯反演、经典公式变换要能熟练灵活的结合使用。

---

Prob 3

给你$\ a,b,c$，求$gcd(i,j,k)=1$的$(i,j,k)$的数量，其中$1\leq i\leq a,1\leq j\leq b,1\leq k\leq c$

这个嘛……╮(╯▽╰)╭还是两种推法：
Method 1:

$$ans=\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c[gcd(i,j,k)=1]$$
$$=\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c\sum_{d\mid gcd(i,j,k)}\mu(d)$$
$$=\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c\sum_{d\mid i\ \wedge\ d\mid j\ \wedge\ d\mid k}\mu(d)$$ \
$$=\sum_d\mu(d)\sum_{i=1}^a[d\mid i]\sum_{j=1}^b[d\mid j]\sum_{k=1}^c[d\mid k]$$
$$=\sum_d\mu(d)\cdot \lfloor\frac{a}{d}\rfloor\cdot\lfloor\frac{b}{d}\rfloor\cdot\lfloor\frac{c}{d}\rfloor$$
接下来怎么做？我就呵呵一笑不说话……
Method 2:
莫比乌斯反演，构造：
$f(x)=\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c[gcd(i,j,k)=x]$
$g(x)=\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c[x\mid gcd(i,j,k)]=\lfloor\frac{a}{x}\rfloor\cdot\lfloor\frac{b}{x}\rfloor\cdot\lfloor\frac{c}{x}\rfloor$
很明显
$g(x)=\sum_{d\mid x}f(d)$
反演
$f(x)=\sum_{x\mid d}\mu(\frac{d}{x})g(d)$
换元，令$d'\equiv \frac{d}{x},d=d'\cdot x$
$f(x)=\sum_{d'}\mu(d')g(d'\cdot x)=\sum_{d'}\mu(d')\cdot \lfloor\frac{a}{d'}\rfloor\cdot\lfloor\frac{b}{d'}\rfloor\cdot\lfloor\frac{c}{d'}\rfloor$

总结一下，我们会发现，莫比乌斯反演虽然有两种形式：

$$g(x)=\sum_{d\mid x}f(d)\Leftarrow\Rightarrow f(x)=\sum_{d\mid x}\mu(d)\cdot g(\frac{x}{d})$$ $$g(x)=\sum_{d\mid x}f(d)\Leftarrow\Rightarrow f(x)=\sum_{x\mid d}\mu(\frac{d}{x})\cdot g(d)$$
但是，实际应用时，第二种形式更加常用，但是换元很重要，不要换错了！

---

Prob 4[BZOJ 3529]

令$F(i)$为$i$的约数和，$q$次给定$\ n,m,a$，求 $$\sum_{i=1}^n\sum_{j=1}^m[F(gcd(i,j))<=a]F(gcd(i,j))\ {\rm mod}\ 2^{31}$$

$n,m\leq 10^5,q\leq 2\times 10^4,a\leq 10^9$

$a$的存在很难受，我们先不考虑$a$的限制
令$g(k)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=k]$，那么

$$ans=\sum_{i=1}^{min(n,m)}F(i)\cdot g(i)$$
$$=\sum_{i=1}^{min(n,m)}F(i)\cdot \sum_{i\mid d}\mu(\frac{d}{i})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$$
$$=\sum_d\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\sum_{i\mid d}F(i)\cdot \mu(\frac{d}{i})$$
很明显，问题的关键就是$\sum_{i\mid d}F(i)\cdot \mu(\frac{d}{i})$这一堆东西了
还是那两个思路：
Method 1:
很明显，$F(x),\mu(x)$都是积性函数，$H(x)=\sum_{i\mid d}F(i)\cdot \mu(\frac{d}{i})$是它们的狄利克雷卷积，也是积性函数
所以，我们可以筛法搞定。
Method 2:
还是那句话，傻瓜也有傻瓜的好处，暴力枚举更新$i$的倍数，$\Theta(N\ \log{N})$解决。
回到原问题上来：$a$的限制怎么办？
我们发现，只有$F(i)\leq a$的$i$才会对答案有贡献
我们离线排序，询问按$a$排序，$i$按$F(i)$排序
每次询问，将符合条件的$i$插入树状数组中维护前缀和
至此，问题完美解决。