0%

ProjectEuler-432

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