本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-09 11:02:14

这题难点子啊与拆开之后怎么整合到一个可以求解的式子。
参考题解 1
参考题解 2

求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m \arphi(ij)$。
注意到 $n$ 比较小。
设 $s(n,m) = \sum\limits_{i=1}^m \arphi(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 \arphi(iab)$
$=a\sum\limits_{i=1}^m\arphi(ib)$
$=a\sum\limits_{i=1}^m\arphi(i\frac{b}{(i,b)}(i,b))$
$=a\sum\limits_{i=1}^m\arphi(i\frac{b}{(i,b)})(i,b)$
$=a\sum\limits_{i=1}^m\arphi(i)\arphi(\frac{b}{(i,b)})(i,b)$
$=a\sum\limits_{i=1}^m\arphi(i)\arphi(\frac{b}{(i,b)})\sum\limits_{d|(i,b)}\arphi(d)$
$=a\sum\limits_{i=1}^m\arphi(i)\sum\limits_{d|(i,b)}\arphi(d)\arphi(\frac{b}{(i,b)})$
$=a\sum\limits_{i=1}^m\arphi(i)\sum\limits_{d|(i,b)}\arphi(\frac{b}{\frac{(i,b)}{d}})$
$=a\sum\limits_{i=1}^m\arphi(i)\sum\limits_{d|(i,b)}\arphi(\frac{b}{d})$
$=a\sum\limits_{d |b}\arphi(\frac{b}{d})\sum\limits_{i=1}^{\lfloor\frac{m}{d}\rfloor}\arphi(di)$
$=a\sum\limits_{d|b}\arphi(\frac{b}{d})S(d,\lfloor \frac{m}{d}\rfloor)$。

我不会证明复杂度，递归到 $n=1$ 就杜教筛，$m=0$ 就返回 $0$。