$$ \begin {aligned} \sum _ {i = 1} ^ n \sum _ {j = 1} ^ m \varphi(ij) & = \sum _ {i = 1} ^ n \sum _ {j = 1} ^ m \frac {\varphi(i) \varphi(j) (i, j)} {\varphi((i, j))} \\ & = \sum _ {d = 1} ^ n \frac d {\varphi(d)} \sum _ {i = 1} ^ n \sum _ {j = 1} ^ m [(i, j) = d] \varphi(i) \varphi(j) \\ & = \sum _ {d = 1} ^ n \frac d {\varphi(d)} \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor } \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor } [(i, j) = 1] \varphi(id) \varphi(jd) \\ & = \sum _ {d = 1} ^ n \frac d {\varphi(d)} \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor } \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor } \sum _ {k | (i, j)} \mu(k) \varphi(id) \varphi(jd) \\ & = \sum _ {d = 1} ^ n \sum _ {k = 1} ^ n \mu(k) \frac d {\varphi(d)} \sum _ {i = 1} ^ {\lfloor \frac n {kd} \rfloor } \sum _ {j = 1} ^ {\lfloor \frac m {kd} \rfloor } \varphi(idk) \varphi(jdk) \\ & = \sum _ {T = 1} ^ n (\mu * \frac {id} {\varphi})(T) \sum _ {i = 1} ^ {\lfloor \frac n T \rfloor } \varphi(iT) \sum _ {j = 1} ^ {\lfloor \frac m T \rfloor } \varphi(jT) \\ \end {aligned} $$
左侧部分的积性函数可以在接受范围内求得，记为 $f$ 。右侧关于 $T$ 和 $\lfloor \frac n T \rfloor $ 记为 $g(a, b)$ ，总状态数有 $n \ln n$ 个可以直接求得。这样可以得到一个 $O(n \ln n + Tn)$ 的做法。
将原式写为：
$$ \sum _ {d = 1} ^ n f(d) g(d, \lfloor \frac n d \rfloor) g(d, \lfloor \frac m d \rfloor) $$
考虑数论分块，对于当前一段 $[l, r]$ ，其 $\lfloor \frac n d \rfloor$ 和 $\lfloor \frac m d \rfloor$ 都相同。需要得到 $\sum _ {i = l} ^ r f(i) g(i, \lfloor \frac n d \rfloor) g(i, \lfloor \frac m d \rfloor)$ 。考虑对于每一组 $(\lfloor \frac n d \rfloor, \lfloor \frac m d \rfloor)$ 预处理 $f(i) g(i, \lfloor \frac n d \rfloor) g(i, \lfloor \frac m d \rfloor)$ 的前缀和。如果全部预处理，时空复杂度都是不可接受的，考虑预处理 $\lfloor \frac n d \rfloor, \lfloor \frac m d \rfloor < B$ 的范围内，那么时空复杂度为 $O(B ^ 2 n)$ ，查询复杂度 $O(\sqrt n)$ 。这样的话剩下的部分依然暴力查询，即 $d \le \frac m B$ 的部分，复杂度 $O(\frac n B)$。
这样复杂度有 $O(n \ln n + n B^ 2 + T(\sqrt n + \frac n B))$ 。当 $n = \sqrt [3] T$ 取到理论最优，为 $O(n \ln n + n T ^ {\frac 2 3} + n ^ {\frac 1 2}T)$ 。