BZOJ3512 DZY Loves Math IV 题解
__vector__
·
·
题解
这题难点子啊与拆开之后怎么整合到一个可以求解的式子。
参考题解 1
参考题解 2
求 \sum\limits_{i=1}^n\sum\limits_{j=1}^m \varphi(ij)。
注意到 n 比较小。
设 s(n,m) = \sum\limits_{i=1}^m \varphi(ni)。
令 n 的质因数分解为 \prod\limits_{i=1}^kd_i^{p_i}。
令 a=\prod\limits_{i=1}^kd_i^{p_i-1},b=\frac{n}{a}。
S(n,m) = \sum\limits_{i=1}^m \varphi(iab)
=a\sum\limits_{i=1}^m\varphi(ib)
=a\sum\limits_{i=1}^m\varphi(i\frac{b}{(i,b)}(i,b))
=a\sum\limits_{i=1}^m\varphi(i\frac{b}{(i,b)})(i,b)
=a\sum\limits_{i=1}^m\varphi(i)\varphi(\frac{b}{(i,b)})(i,b)
=a\sum\limits_{i=1}^m\varphi(i)\varphi(\frac{b}{(i,b)})\sum\limits_{d|(i,b)}\varphi(d)
=a\sum\limits_{i=1}^m\varphi(i)\sum\limits_{d|(i,b)}\varphi(d)\varphi(\frac{b}{(i,b)})
=a\sum\limits_{i=1}^m\varphi(i)\sum\limits_{d|(i,b)}\varphi(\frac{b}{\frac{(i,b)}{d}})
=a\sum\limits_{i=1}^m\varphi(i)\sum\limits_{d|(i,b)}\varphi(\frac{b}{d})
=a\sum\limits_{d |b}\varphi(\frac{b}{d})\sum\limits_{i=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(di)
我不会证明复杂度，递归到 $n=1$ 就杜教筛，$m=0$ 就返回 $0$。