好久没做题了，前一段时间旅游了一小会儿然后趁着 **USC 的机会溜回家开始了长达七天的暑假生活。

闲着无聊做了一下 PE-432 ……

Problem

令

$$S(n, m) = \sum\_{i=1}^{m} \phi(n \times i)$$

求 $S(510510, 10^{11})$

Solution

令 $n = pq$ ，且 $p$ 为质数，有

$$S(n, m) = (p - 1) S(q, m) + S(n, \lfloor \frac{m}{p} \rfloor)$$

于是我们只要计算

$$S(1, m) = \sum\_{i = 1}^m \phi(i)$$

即可。

线性筛法可以去死了。我们可以采用 @dyh 的理性愉悦 $O(n^{\frac{2}{3}})$ 的方法：

令 $S_f$ 表示函数 $f$ 的前缀和函数，即

$$S_f(n) = \sum_{i = 1}^n f(i),$$

我们要求 $S_{\phi} (n)$ 。

令 $g_n = \sum_{d|n} f_n$ 于是有

$$S*g(n) = \sum*{i = 1}^n \sum*{d|i} f(d) = \sum*{i=1}^n S_f(\lfloor \frac{n}{i} \rfloor)$$

这个等式只要注意到每个 $f(i)$ 被加的次数都是 $\lfloor\frac{n}{i}\rfloor$ 就好了。

如果我们能够快速计算 $S_g(n)$ ，就可以利用

$$S*f(n) = S_g(n) - \sum*{i = 2}^n S_f(\lfloor \frac{n}{i} \rfloor)$$

来计算 $S_f(n)$ 了。

当 $f(n) = \phi(n)$ 时， $g(n) = \sum_{d|n} f_n = n$ ，$S_g(n) = \frac{1}{2} n(n+1)$ 。我们用筛法算出 $i \leq n^{\frac{2}{3}}$ 时的 $S_f(i)$ ，其余的暴力记忆化递归做下去，复杂度是 $O(n^{\frac{2}{3}})$ 。

我一开始把 $m$ 看成了 $10^{14}$ 跑了 20min 才跑出来， $m = 10^{11}$ 时只要 3s 就可以了……