## 解题思路

$S(n,m)=\prod_{i=1}^n\prod_{j=1}^m[i,j]^{[i,j]}$

$\frac{S(r,r)S(l-1,l-1)}{S(l-1,r)^2}$

\begin{aligned} S(n,m)&=\prod_{i=1}^n\prod_{j=1}^m[i,j]^{[i,j]}\\ &=\prod_{i=1}^n\prod_{j=1}^m\left(\frac{ij}{(i,j)}\right)^{\frac{ij}{(i,j)}}\\ &=\prod_{d=1}^n\prod_{i=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{d}\rfloor}(ijd)^{ijd[(i,j)=1]}\\ &=\prod_{d=1}^n\prod_{e=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{i=1}^{\lfloor\frac{n}{de}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{de}\rfloor}(ijde^2)^{ijde^2\mu(e)}\\ &\xlongequal{D=de}\prod_{D=1}^n\prod_{e\mid D}\prod_{i=1}^{\lfloor\frac{n}{D}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{D}\rfloor}(ijDe)^{ijDe\mu(e)} \end{aligned}

$S(n,m)=\prod_{d=1}^n\prod_{e\mid d}\prod_{i=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{d}\rfloor}(ijde)^{ijde\mu(e)}$

\begin{aligned} S(n,m)&=\prod_{d=1}^n\prod_{e\mid d}\prod_{i=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{d}\rfloor}(ijde)^{ijde\mu(e)}\\ &=\prod_{d=1}^n\prod_{e\mid d}\left(\prod_{i=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{d}\rfloor}(ij)^{ij}\right)^{de\mu(e)}\prod_{d=1}^n\prod_{e\mid d}(de)^{de\mu(e)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij}\\ &\xlongequal[s(n)=\sum_{i=1}^n i=\frac{n(n+1)}{2}]{H(n)=\prod_{i=1}^n i^i}\prod_{d=1}^n\prod_{e\mid d}\left(H\left(\left\lfloor\frac{n}{d}\right\rfloor\right)^{s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}H\left(\left\lfloor\frac{m}{d}\right\rfloor\right)^{s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)}\right)^{de\mu(e)}\prod_{d=1}^n\prod_{e\mid d}(de)^{de\mu(e)s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}\\ &\xlongequal[h(n)=(\{\operatorname{id}\mu\}*\{1\})(n)]{g(m,n)=H(n)^{s(m)}H(m)^{s(n)}}\prod_{d=1}^ng\left(\left\lfloor\frac{n}{d}\right\rfloor,\left\lfloor\frac{m}{d}\right\rfloor\right)^{dh(d)}\prod_{d=1}^nd^{dh(d)s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}\prod_{d=1}^n\prod_{e\mid d}e^{de\mu(e)s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}\\ &\xlongequal{k(n)=\prod_{e\mid n}e^{e\mu(e)}}\prod_{d=1}^ng\left(\left\lfloor\frac{n}{d}\right\rfloor,\left\lfloor\frac{m}{d}\right\rfloor\right)^{dh(d)}\prod_{d=1}^nd^{dh(d)s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}\prod_{d=1}^nk(d)^{ds\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}\\ &=\prod_{d=1}^n\left(g\left(\left\lfloor\frac{n}{d}\right\rfloor,\left\lfloor\frac{m}{d}\right\rfloor\right)^{h(d)}\left(d^{h(d)}k(d)\right)^{s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}\right)^{d}\\ &=\prod_{d=1}^ng\left(\left\lfloor\frac{n}{d}\right\rfloor,\left\lfloor\frac{m}{d}\right\rfloor\right)^{dh(d)}\prod_{d=1}^n\left(d^{dh(d)}k(d)^d\right)^{s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)} \end{aligned}

## 时间复杂度

$$O(n\log n+t\sqrt{n}\log n)$$

Show code