$$
\begin {aligned}
\sum _ {i = 1} ^ n \sum _ {j = 1} ^ m \varphi (\frac {\mathrm{lcm}(i, j)} {(i, j)}) & = \sum _ {i = 1} ^ n \sum _ {j = 1} ^ m \varphi (\frac i {(i, j)} \frac j {(i, j)}) \\
& = \sum _ {i = 1} ^ n \sum _ {j = 1} ^ m \frac {\varphi(\frac i {(i, j)})\varphi(\frac j {(i, j)})(\frac i {(i, j)}, \frac j {(i, j)})}{\varphi((\frac i {(i, j)}, \frac j {(i, j)}))} \\
& = \sum _ {i = 1} ^ n \sum _ {j = 1} ^ m \varphi(\frac i {(i, j)})\varphi(\frac j {(i, j)}) \\
& = \sum _ {d = 1} ^ n \sum _ {i = 1} ^ n \sum _ {j = 1} ^ m \varphi(\frac i d)\varphi(\frac j d) [(i, j) = d] \\
& = \sum _ {d = 1} ^ n \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor } \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor } \varphi(i)\varphi(j) [(i, j) = 1] \\
& = \sum _ {d = 1} ^ n \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor } \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor } \varphi(i)\varphi(j) \sum _ {k | (i, j)} \mu(k) \\
& = \sum _ {d = 1} ^ n \sum _{k = 1} ^ n \mu(k) \sum _ {i = 1} ^ {\lfloor \frac n {kd} \rfloor } \sum _ {j = 1} ^ {\lfloor \frac m {kd} \rfloor } \varphi(ik)\varphi(jk) \\
& = \sum _ {T = 1} ^ n \sum _ {d | T} \mu(d) \sum _ {i = 1} ^ {\lfloor \frac n T \rfloor } \varphi(id) \sum _ {j = 1} ^ {\lfloor \frac m T \rfloor } \varphi(jd) \\
\end {aligned}
$$
记 $g(a, b) = \sum _ {i = 1} ^ b \varphi(ia)$ ，状态共 $n \ln n$ 种，可以直接预处理出来。这样暴力可以得到一个 $O(Tn\ln n)$ 的算法。
记 $c(x, i, j) = \sum _ {d | x} \mu(d) g(d, \lfloor \frac n x \rfloor) g(d, \lfloor \frac m x \rfloor)$ 。
考虑数论分块，对于每一组 $(\lfloor \frac n x \rfloor, \lfloor \frac m x \rfloor)$ ，维护 $c(x, \lfloor \frac n x \rfloor, \lfloor \frac m x \rfloor)$ 的前缀和。考虑维护 $\lfloor \frac n x \rfloor < B$ 的部分，剩下的暴力计算。$B = \sqrt[3]T$ 左右最优。
查看代码
1 |