如果 $x | i \wedge y | j$ ，那么一定有 $xy |ij$ ， 即 $xy$ 是 $ij$ 的约数，对答案有贡献。但是如果直接这样计算可能会出现重复的，如 $4 \times 6 = 24$ ，$3 \times 8 = 24$ ，所以我们要求 $x \bot y$ 时才计算答案，对于 $i, j$ 均有的质因子，尽可能在 $i$ 中取得，如果不够在 $j$ 中取（此时 $i$ 中取完了，不妨令其这个质因子的指数为 $0$ ），这样，每一个约数都可以被不重不漏地表示出来。因此 $d(i j) = \displaystyle \sum_{x |i} \sum _{y | j} [gcd(x, y) = 1]$ 。
答案为：
$$
\begin {aligned}
\sum _ {i = 1} ^ N \sum _ {j = 1} ^ M d(i j) = & \sum _ {i = 1} ^ N \sum _ {j = 1} ^ M \sum _ {x | i} \sum _ {y | j} [gcd(x, y) = 1]\\
= & \sum _ {i = 1} ^ N \sum _ {j = 1} ^ M \sum _ {d = 1} ^{min(N, M)} \mu (d) \sum _ {x | i \wedge d | x} \sum_{y | j \wedge d | y} \\
= &\sum _ {d = 1} ^ {min(N, M)} \mu(d) \sum _ {i = 1} ^ {\frac M d} \left \lfloor \frac M {di} \right \rfloor \sum _ {j = 1} ^{\frac N d}\left \lfloor \frac N {j d} \right \rfloor
\end {aligned}
$$
记 $h(x) = \displaystyle \sum_{i = 1} ^ x \left \lfloor \frac x i \right \rfloor$ ，则答案为：
$$
\sum_{i = 1} ^ n \sum_{j = 1} ^ m d(i j) = \sum_{d = 1} ^ {min(N, M)} \mu(d) h(\frac N d) h (\frac M d)
$$
其中 $h _ i$ 可以用数论分块预处理，最终计算答案的时候可以用数论分块计算。
查看代码
1 |
|