ProjectEuler 432 - Totient sum

好久没做题了，前一段时间旅游了一小会儿然后趁着 **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 就可以了……