数学草稿

P13645 Totient with Divisors

\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)\sigma(ij)&=\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)\sum_{a|i}\sum_{b|j}\frac{ib}{a}\times[a\perp b]\\ &=\sum_{o=1}^{n}\mu(o)o\times (\sum_{i=1}^{\left\lfloor\frac{n}{o}\right\rfloor}i\varphi(io)\lambda(i))\times (\sum_{j=1}^{\left\lfloor\frac{m}{o}\right\rfloor}\sigma(j)\varphi(jo))\\ \lambda(n)&=\sum_{d|n} \frac{1}{d} \end{aligned} \]

那么对于两个括号内的是容易 \(n\log n\) 预处理出来的，则每次对 \(o\) 整除分块有询问 \(\sum_{o=1}^p \mu(o)o\times f(X,o)\times g(Y,o)\)，共询问 \(O(T\sqrt n)\) 次。
不会了。\(\color{#FF9696}\mathtt \Gamma\)

P4240 毒瘤之神的考验

令 \(f(i,j)=\varphi(ij)\)，即询问 \(S_f(n,m)\)。
令 \(g(i,j)=\varphi(i)\varphi(j)\)。
有 \(\mathcal{F}_p(u,v)=\frac{uvp(p-1)}{(1-up)(1-vp)}+\frac{u(p-1)}{1-up}+\frac{v(p-1)}{1-vp}+1\)，\(\mathcal{G}_p(u,v)=\frac{uv(p-1)^2}{(1-up)(1-vp)}+\frac{u(p-1)}{1-up}+\frac{v(p-1)}{1-vp}+1\)，容易发现 \(\mathcal{H}_p=\mathcal{F}_p/\mathcal{G}_p=1+\frac{uv(p-1)}{(1-u)(1-v)}\)。

由于 \(h*g=f\)，而 \(f(1,p^k)=g(1,p^k)\)，有 \(h(1,p^k)=h(p^k,1)=0\)。那么 \(h\) 非零的位置只有 \(\sqrt {nm}\) 个。暴搜则有 \(O(n+m+\sqrt{nm})\) 的复杂度。

多组询问：设定阈值 \(B\)，对于 \(xy\le B\) 的直接暴力计算，复杂度 \(O(\sqrt B)\)。
对于 \(xy>B\)，他对询问 \((n,m)\) 的贡献是 \(h(x,y)S_\varphi(\left\lfloor\frac{n}{x}\right\rfloor)S_\varphi(\left\lfloor\frac{m}{y}\right\rfloor)\)，有 \(O(\frac{n^2}{xy})\) 个不同的矩形，离线二维数点。