题目描述
栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。
栋栋的植物种得非常整齐，一共有 $n$ 列，每列有 $m$ 棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标 $(x,y)$ 来表示，其中 $x$ 的范围是 $1$ 至 $n$，表示是在第 $x$ 列，$y$ 的范围是 $1$ 至 $m$，表示是在第 $x$ 列的第 $y$ 棵。
由于能量汇集机器较大，不便移动，栋栋将它放在了一个角上，坐标正好是 $(0,0)$。
能量汇集机器在汇集的过程中有一定的能量损失。如果一棵植物与能量汇集机器连接而成的线段上有k棵植物，则能 量的损失为 $2k+1$。例如，当能量汇集机器收集坐标为 $(2,4)$ 的植物时，由于连接线段上存在一棵植物 $(1,2)$，会产生 $3$ 的能量损失。注意，如果一棵植物与能量汇集机器连接的线段上没有植物，则能量损失为 $1$。现在要计算总的能量损失。
$1\le n,m\le 100,000$。
算法分析
首先从 $(0,0)$ 到 $(x,y)$ 路径上的格点个数为 $gcd(x,y)-1$，因为每走 $(\frac{x}{gcd(x,y)},\frac{y}{gcd(x,y)})$ 就会有一个格点，而不包括端点。
所以问题所求即 $\sum_{i=1}^{n}\sum_{j=1}^m(2(gcd(i,j)-1)+1)=\sum_{i=1}^{n}\sum_{j=1}^m(2gcd(i,j)-1)$。
做法一：莫比乌斯反演
将式子转化一下变成 $2\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)-n\times m$，考虑用莫比乌斯反演推出 $\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)$ 的值。
枚举 $gcd(i,j)$ 的值得到 $\sum_{g=1}^{min{n,m}}g\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=g]=\sum_{g=1}^{min{n,m}}g\sum_{i=1}^\frac{n}{g}\sum_{j=1}^\frac{m}{g}[gcd(i,j)=1]$。
莫比乌斯反演得原式等于 $\sum_{g=1}^{min{n,m}}g\sum_{i=1}^\frac{n}{g}\sum_{j=1}^\frac{m}{g}\sum_{d|gcd(i,j)}\mu(d)=\sum_{g=1}^{min{n,m}}g\sum_{i=1}^\frac{n}{g}\sum_{j=1}^\frac{m}{g}\sum_{d|i且 d|j}\mu(d)$。
枚举 $d$ 的值得到 $\sum_{g=1}^{min{n,m}}g\sum_{d=1}^{\lfloor\frac{min{n,m}}{g}\rfloor}\mu(d)\lfloor\frac{n}{gd}\rfloor\lfloor\frac{n}{gd}\rfloor$，然后我到这里就不会推了？？？
其实这里就可以直接算了，根据调和级数，时间复杂度大约是 $O(n\ln{n})$。注意初始化 $mu[1]=1$。
做法二：容斥原理
洛谷题解上还有一种高妙的做法：容斥原理。
设 $f[x]$ 表示 $i\in[1,n],j\in[1,m]$ 时 $gcd(i,j)=x$ 的个数，则 $f[x]=\lfloor\frac{n}{x}\rfloor\times\lfloor\frac{m}{x}\rfloor$，然而这里面还可能包括 $gcd(i,j)=2x$、$gcd(i,j)=3x$ 之类的情况，这样只需再枚举 $x$ 的倍数，把这些情况减去即可。
由于要确保之前的情况已经计算过，因此需要倒序求。
根据调和级数，时间复杂度为 $O(n\ln n)$。
代码实现
做法一：莫比乌斯反演
1 |
|
做法二：容斥原理
1 |
|