问题分析

本题要求计算所有植物到能量汇集机器（坐标$(0,0)$）的能量损失总和。能量损失的关键在于确定植物$(x,y)$与$(0,0)$连线上的植物数量$k$，损失为$2k + 1$。

核心观察：

• 两点$(0,0)$和$(x,y)$连线上的植物数量$k$，等价于满足“存在$d>0$，使得$d$是$x$和$y$的公因数”的情况数。更准确地说，$k = \gcd(x,y) - 1$（因为$\gcd(x,y)$表示连线上除端点外的植物数量，所以总植物数为$\gcd(x,y) - 1$）。
• 能量损失为$2k + 1 = 2(\gcd(x,y) - 1) + 1 = 2\gcd(x,y) - 1$。

因此，总能量损失可表示为：

$$\sum_{x=1}^n \sum_{y=1}^m (2\gcd(x,y) - 1) = 2\sum_{x=1}^n \sum_{y=1}^m \gcd(x,y) - nm $$

问题转化为计算$\sum_{x=1}^n \sum_{y=1}^m \gcd(x,y)$，再通过上述公式得到最终结果。

莫比乌斯反演推导

我们需要计算$\sum_{x=1}^n \sum_{y=1}^m \gcd(x,y)$。

利用数论中的结论，通过莫比乌斯反演和整除分块优化：

• 令$f(d) = \sum_{x=1}^n \sum_{y=1}^m [\gcd(x,y) = d]$，表示$\gcd(x,y)$恰好为$d$的$(x,y)$对数。
• 则$\sum_{d=1}^{\min(n,m)} d \cdot f(d)$即为所求的$\sum\gcd(x,y)$。

进一步推导：

• 令$g(d) = \sum_{k=1}^{\lfloor \min(n,m)/d \rfloor} f(kd)$，即$\gcd(x,y)$是$d$的倍数的$(x,y)$对数，显然$g(d) = \lfloor \frac{n}{d} \rfloor \cdot \lfloor \frac{m}{d} \rfloor$。
• 根据莫比乌斯反演，$f(d) = \sum_{k=1}^{\lfloor \min(n,m)/d \rfloor} \mu(k) \cdot g(kd)$，其中$\mu$是莫比乌斯函数。

最终，$\sum_{d=1}^{\min(n,m)} d \cdot f(d) = \sum_{d=1}^{\min(n,m)} d \cdot \sum_{k=1}^{\lfloor \min(n,m)/d \rfloor} \mu(k) \cdot \lfloor \frac{n}{kd} \rfloor \cdot \lfloor \frac{m}{kd} \rfloor$。

令$t = kd$，则上式可转化为$\sum_{t=1}^{\min(n,m)} \lfloor \frac{n}{t} \rfloor \cdot \lfloor \frac{m}{t} \rfloor \cdot \sum_{d|t} d \cdot \mu(\frac{t}{d})$。

注意到$\sum_{d|t} d \cdot \mu(\frac{t}{d})$是积性函数，且其值等于$\varphi(t)$（欧拉函数）。因此，最终简化为：

$$\sum_{t=1}^{\min(n,m)} \lfloor \frac{n}{t} \rfloor \cdot \lfloor \frac{m}{t} \rfloor \cdot \varphi(t) $$

算法实现

代码中通过整除分块和预处理欧拉函数的思想（代码中通过类似筛法的方式计算$f[i]$，其本质等价于欧拉函数的贡献）来高效计算上述求和式：

• 枚举$d$从$\min(n,m)$到$1$，计算$f[d] = \lfloor \frac{n}{d} \rfloor \cdot \lfloor \frac{m}{d} \rfloor - \sum_{k=2d}^{n} f[k]$（这里利用了容斥，减去所有$k$是$d$倍数的情况，等价于莫比乌斯反演的推导）。
• 最终结果通过$2 \times \sum (f[i] \cdot i) - nm$得到，其中$nm$是原式中“$-1$”的累加（总共有$nm$项，每项减$1$）。

该方法的时间复杂度为$O(\min(n,m) \log \min(n,m))$，可高效处理$n,m \leq 10^5$的数据规模。

算法标签

• 数论（莫比乌斯反演）
• 整除分块

总结

本题通过数论中的莫比乌斯反演和欧拉函数，结合整除分块的优化思想，将复杂的双重求和问题转化为可高效计算的形式，最终在线性时间复杂度的级别内解决了问题。