数学 · 初探莫比乌斯2
lg_zhou
·
·
个人记录
数学是困难的，但也是美丽的。你已经叩开了莫反的大门，你将马上感受到它无穷的魅力。
请确保已经学会 这里 的全部内容。我们只需要用这里的那一条性质，不需要卷积等其他知识。其实这条性质就已经能解决我们现在的大部分问题。
P2257 YY的GCD
这题和 P3455 [POI2007]ZAP-Queries 非常像。我们在 上篇 已经讲过，默认大家已经会 P3455 这一题。
设质数为 k，如果暴力枚举 k，那做法和 P3455 就一模一样。先将 gcd(x,y) = k 的问题转化为互质问题。
我们暴力写出式子：
\sum\limits_{x = 1}^{n/k}
\sum\limits_{y=1}^{m/k}
\sum\limits_{d|gcd(x,y)}\mu(d)$ $(k \in prime)
转化为枚举 d，求满足要求的 x,y 对数。
\sum\limits_{d = 1}^{min(n,m)}\mu(d)
\left\lfloor\dfrac{n}{kd}\right\rfloor
\left\lfloor\dfrac{m}{kd}\right\rfloor$ $(k \in prime)
这时候我们继续考虑优化。我们其实是枚举 k 和 d，将和 kd 有关的式子累计进入答案。我们反过来，尝试枚举 T=kd 与 k，并直接算出 d。
\left\lfloor\dfrac{n}{T}\right\rfloor
\left\lfloor\dfrac{m}{T}\right\rfloor
\sum\limits_{k | T}\mu(\dfrac{T}{k})
$ $(k \in prime)
前面依旧整除分块，而我们惊喜的发现后面的
对于每个 $i$，找出所有 $\mu(\dfrac{i}{p_j}) (p_j|i)$ 累加就行。 还是反着想，我们先枚举 $p_j$，枚举它的 $k$ 倍，将 $t[p_j \times k]$ 累加 $\mu(k)$ 即可。
***
#### [P2398 GCD SUM](https://www.luogu.com.cn/problem/P2398)
依旧是枚举 $g=gcd(i,j)$ , 看有多少组 $i,j$ 满足条件。（都套路了）
答案转化为
$\sum\limits_{g = 1}^{n}
\sum\limits_{i=1}^{n}
\sum\limits_{j=1}^{n}
[gcd(i,j)=g] \times g
(如果 gcd(i,j) = g，就说明 g 在答案的系数要加1，答案就加 g)
发现和上一题一模一样好嘛！！！只不过 g 不一定是质数罢了。
\sum\limits_{i = 1}^{n/g}
\sum\limits_{j = 1}^{n/g}
\sum\limits_{d|gcd(i,j)}\mu(d)
\sum\limits_{d = 1}^{n/g}\mu(d)
\left\lfloor\dfrac{n}{gd}\right\rfloor
\left\lfloor\dfrac{n}{gd}\right\rfloor
\left\lfloor\dfrac{n}{T}\right\rfloor
\left\lfloor\dfrac{n}{T}\right\rfloor
\sum\limits_{g | T}\mu(\dfrac{T}{g}) \times g
这种做法的复杂度已经低于题目要求。（这题直接枚举 $g$ 就能过），提交可以参考 [UVA11426 拿行李（极限版） GCD - Extreme (II)](https://www.luogu.com.cn/problem/UVA11426) 这一题数据范围更大，并且这两题只有范围不同。
是不是发现本质都是差不多的？
***
#### [P1829 [国家集训队]Crash的数字表格 / JZPTAB](https://www.luogu.com.cn/problem/P1829)
本题求 $\sum\limits_{i=1}^{n}
\sum\limits_{j=1}^{m}lcm(i,j)$ ， $lcm(i,j)$ 不会求，就转化成 $\dfrac{i \times j}{gcd(i,j)}
= \sum\limits_{i=1}^{n}
\sum\limits_{j=1}^{m}\dfrac{i \times j}{gcd(i,j)}
套路，改成枚举 g = gcd(i,j)，找到一组满足条件的 i,j。并将答案累计 \dfrac{i \times j}{g}。
\sum\limits_{g|i}^{n}
\sum\limits_{g|j}^{m}
[gcd(i,j)=g] \times \dfrac{i \times j}{g}
是不是又很熟悉？！跟上两题几乎一样，但是最后一项和 i,j 有关，导致可能不能直接累加答案，我们继续化简。我们其实枚举 i 枚举的是 i = g, 2g,3g…… 我们改成枚举 i 为 1,2,3，并将后面的 i 替换成 ig , j 同理。
\sum\limits_{i=1}^{n/g}
\sum\limits_{j=1}^{m/g} \times i \times j
\sum\limits_{d|gcd(i,j)}\mu(d)
由于式子中带 i,j ，每个 i,j 的贡献都不同，在枚举 d 时我们不能简单地将其化为 \left\lfloor\dfrac{n}{gd}\right\rfloor 个 i 这样的形式。
\sum\limits_{d = 1}^{n/g}\mu(d)
\sum\limits_{d|i}^{n/g}
\sum\limits_{d|j}^{m/g} \times i \times j
$=\sum\limits_{g = 1}^{min(n,m)}g \times
\sum\limits_{d = 1}^{n/g}\mu(d)
\sum\limits_{i}^{n/gd}
\sum\limits_{j}^{m/gd} \times i \times j \times d^2
我们细细观察上面这个式子，发现当 n/g 不变时，
\sum\limits_{i}^{n/gd}
\sum\limits_{j}^{m/gd} \times i \times j$ 不变， 而 $\sum g$ 可以预处理，一次整除分块来了。
而当 $n/gd$ 不变时 $\sum\limits_{i}^{n/gd}
\sum\limits_{j}^{m/gd} \times i \times j$ 也不变。 而 $\sum\ \mu(d) \times d^2$ 也可以预处理！第二次整除分块来了！
就这样，两次整除分块，漂亮的解决了这道题。
***
#### [SP5971 LCMSUM - LCM Sum](https://www.luogu.com.cn/problem/SP5971)
然而有的时候我们也不能太过套路，上来就反演，而丧失了更简便的解法。比如这道题，很显然是上一道题的弱化版。
该上的套路还是要上的：
$=\sum\limits_{i=1}^{n}
\dfrac{i\times n}{gcd(i,n)}
\sum\limits_{g|i}^{n}
[gcd(i,n)=g] \times \dfrac{i \times n}{g}
g|i$ 很烦，把它处理掉，后面的 $i$ 都换成 $ig
\sum\limits_{i=1}^{n/g}
[gcd(ig,n) = g] \times i
\sum\limits_{i=1}^{n/g}
[gcd(i,n/g) = 1] \times i
我们发现 \sum\limits_{i=1}^{n/g}
[gcd(i,n/g) = 1] \times i 这个式子很熟悉。意思是如果 i,n/g 互质，就把答案累计 i 的贡献。等价于求 1~n/g 中与 n/g 互质的数的和。
如果你发现不熟悉，请看看 欧拉函数 的第一条性质。
那么原式就化为
\varphi(n/g) \times (n/g)/2
后面的式子可以预处理。
虽然没用到莫比乌斯，但大体思路和上面几道题极其相似。当你发现一个个数学模块相互联系的时候，会不会感到非常神奇？不会。OI 考数学就离谱
好吧，无论如何，我相信我们都已经对莫比乌斯有了初步的了解。
在这里把 题单 分享给大家。
~~8888