$$ \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 \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)$ 的前缀和，时空复杂度为 $O(B n \ln B)$。考虑维护 $\lfloor \frac n x \rfloor < B$ 的部分，剩下的暴力计算，将 $i$ 的约数个数级别视为 $\sqrt i$ ，那么复杂度级别为 $O((\frac n B) ^ {\frac 3 2})$。$B = \sqrt[3]T$ 左右最优。