目前看起来题解的时间复杂度好像都不太正确？

将式子推到

$$\sum_{T=1} f(T)g(\lfloor\frac{n}{T}\rfloor,T)g(\lfloor\frac{m}{T}\rfloor,T)$$

形式后，对 $i,j \le B$ 预处理

$$S(i,j,T)=\sum_{t=1}^T f(t)g(i,t)g(j,t)$$

其中有限制 $iT,jT \le n$。（这里认为 $n,m$ 同阶） 计算 $S$ 的状态数，有

$$\mathcal{O}(\sum_{i=1}^B\sum_{j=1}^B \frac{n}{\max(i,j)})=\mathcal{O}(2\sum_{i=1}^B \sum_{j=1}^i\frac{n}{i})=\mathcal{O}(\sum_{i=1}^B \frac{n}{i}\times i)=\mathcal{O}(nB)$$

那么总时间复杂度为

$$\mathcal{O}(n \log n+nB+T(\sqrt n+\frac{n}{B}))$$

令 $B = \sqrt T$ 可以得到最优复杂度

$$\mathcal{O}(n \log n+n\sqrt T+T \sqrt n)$$