神仙莫比乌斯反演。
有个结论。
(varphi(i imes j) = huge{left(frac{varphi(i) imes varphi(j) imes gcd(i,j)}{varphi(gcd(i,j))} ight)})
首先假设 (nleq m)
(sum_i sum_j varphi(i imes j) = sum_i sum_j {large left(frac{varphi(i) imes varphi(j) imes gcd(i,j)}{varphi(gcd(i,j))} ight)})
枚举(gcd)！
(sum_d sum_i sum_j frac{varphi(i) imes varphi(j) imes gcd(i,j)}{varphi(gcd(i,j))}[gcd(i,j) = d])
然后
(sum_d {left(frac{d}{varphi(d)}
ight)} sum_i^{frac{n}{d}} sum_j^{frac{m}{d}}varphi(i imes d) varphi(j imes d)[gcd(i,j) = 1])
发现 (gcd) 可以用 (mu) 搞
(sum_{d|x} mu(d) = [x=1])
(sum_d {left(frac{d}{varphi(d)} ight)}sum_i^{frac{n}{d}} sum_j^{frac{m}{d}}varphi(i imes d) varphi(j imes d){left(sum_{k|gcd(i,j)} mu(k) ight)})
然后顺手枚举一波 (k)！
(sum_d {left(frac{d}{varphi(d)} ight)} sum_{k}^{frac{n}{d}}mu(k) sum_{i}^{frac{n}{kd}}sum_j^{frac{m}{kd}}varphi(i imes kd) imes varphi(j imes kd))
改变枚举顺序，令 (T=k imes d)
(sum_T sum_{k|T} mu(frac{T}{k}) frac{d}{varphi(d)} sum_i^{frac{n}{T}} sum_j^{frac{m}{T}} varphi(i imes T) imes varphi(j imes T))
然后我们搞搞 (F(T) = sum_T sum_{k|T} mu(frac{T}{k}))
((T, n, m) = sum_i^{frac{n}{T}} sum_j^{frac{m}{T}} varphi(i imes T) imes varphi(j imes T))
发现其实可以令 (G(x, y) = sum_i^x varphi(i imes y))
(G(x, y) = G(x - 1, y) + varphi(xy))
然后整个式子就变成了 (sum_T F(T) imes G(frac{n}{T},T) imes G(frac{m}{T},T))
(G) 可以直接暴力算，因为这个玩意是调和级数的。
但是发现这个答案数组不能搞得太大，所以需要一个根号分治，(leq B) 的部分暴力，(geq B+1) 的整除分块。