遇到了一些奇怪的需求。
大概就是需要对一些级数做渐进，但是只能用初等方法。
\(\sum \limits_{i = 1} ^{n} \frac{1}{i}\)
这是我们经典的调和级数啊。
考虑我们按照 \(\log i\) 进行分组。
\(\sum \limits _{i = 1} ^{n} \frac{1}{i} = \sum \limits _{s = 0} ^{\log n} \sum \limits _{k = 2^s} ^{2^{s + 1} - 1} \frac{1}{k}\)
考虑每一组我们向上放缩到 \(\frac{1}{2^s}\)，向下放缩到 \(\frac{1}{2^{s+1}}\)
然后就有 \(\sum \limits _{s = 0} ^{\log n} \sum \limits _{k = 2^s} ^{2^{s + 1} - 1} \frac{1}{2^{s+1}} < \sum \limits _{s = 0} ^{\log n} \sum \limits _{k = 2^s} ^{2^{s + 1} - 1} \frac{1}{k} < \sum \limits _{s = 0} ^{\log n} \sum \limits _{k = 2^s} ^{2^{s + 1} - 1} \frac{1}{2^s}\)
因此得到 \(\sum \limits _{s = 0} ^{\log n} \sum \limits _{k = 2^s} ^{2^{s + 1} - 1} \frac{1}{k} \in \left[\frac{1}{2} \log n, \log n \right]\)
综上所述，\(\sum \limits _{i = 1} ^{n} \frac{1}{i} = \Theta (\log n)\)
\(\sum \limits _{i = 1} ^{n} \omega(i)\)
其实就是埃氏筛的复杂度说是。
我们需要考察 \(p(n) = \Theta(n \log n)\) 以及 \(\pi(n) = \Theta(\frac{n}{\log n})\)
首先将原式改写成 \(\sum \limits _{i = 1} ^{\pi (n)} \frac{n}{p(i)}\)
由于 \(p(n)\) 和 \(\pi(n)\) 我们都只有渐进结果。所以考虑先丢掉前 \(\Theta (\log \log n)\) 项的结果。这部分并不会超过 \(O(n \log \log n)\)
后面的部分就可以直接把 \(p(n) = n \log n\) 和 \(\pi(n) = \frac{n}{\log n}\) 代入了。
代入之后得到 \(\sum \limits _{i = \log \log n} ^{\frac{n}{\log n}} \frac{n}{i \log i}\)
为了方便处理，我们先进行一步放缩：
\(n \sum \limits _{i = \log \log n} ^{\sqrt n} \frac{1}{i \log i} < n \sum \limits _{i = \log \log n} ^{\frac{n}{\log n}} \frac{1}{i \log i} < n \sum \limits _{i = \log \log n} ^{n} \frac{1}{i \log i}\)
最后可以说明的是，第一部分和第三部分只相差常数倍。因此我们求解第三部分即可。
同样的，按照 \(\log i\) 分组。
\(n \sum \limits _{i = \log \log n} ^{n} \frac{1}{i \log i} = n \sum \limits _{s = \log \log \log n} ^{\log n} \sum \limits _{k = 2^s} ^{2^{s + 1} - 1} \frac{1}{k \log k}\)
然后将 \(k \log k\) 向上放缩至 \(s2^{s + 2}\)，向下放缩至 \(s2^s\)。
于是最后会有 \(n \sum \limits _{s = \log \log \log n} ^{\log n} \frac{1}{4s} < n \sum \limits _{s = \log \log \log n} ^{\log n} \sum \limits _{k = 2^s} ^{2^{s + 1} - 1} \frac{1}{k \log k} < n \sum \limits _{s = \log \log \log n} ^{\log n} \frac{1}{s}\)
这便是我们第一部分的调和级数求和了。得到 \(\left[ \frac{1}{4} n \log \log n, n \log \log n \right]\)
于是得出结论，\(\sum \limits _{i = 1} ^{n} \omega (i) = \Theta (n \log \log n)\)
\(\sum \limits _{i = 1} ^{n} \omega^2 (i)\)
这个题的复杂度说是。
直接拆解即可。
注意到原式可以写成 \(\sum \limits _{i \in P} \sum \limits _{j \in P} \frac{n}{ij} - \sum \limits _{i \in P} \frac{n}{i^2}\)。
（这个是考虑把 \(\omega (i)\) 的贡献拆解到每对本质不同质因子的乘积上面了）
前面那一项的做法和上一个问题完全一致，求出来即为 \(\Theta (n \log^2 \log n)\)，我们来考察一下后面那一项吧。
首先放缩成好处理的样子，\(n < \sum \limits _{i \in P} \frac{n}{i^2} < \sum \limits _{i \ge 1} \frac{n}{i^2}\)
我们只需要证明 \(\sum \limits _{i \ge 1} \frac{1}{i^2} = \Theta(1)\) 即可。
按照 \(\log i\) 分组是万能的说是。
于是乎 \(\sum \limits _{s \ge 0} \sum \limits _{i = 2^s} ^{2^{s + 1} - 1} \frac{1}{2^{2s + 2}} < \sum \limits _{s \ge 0} \sum \limits _{i = 2^s} ^{2^{s + 1} - 1} \frac{1}{i^2} < \sum \limits _{s \ge 0} \sum \limits _{i = 2^s} ^{2^{s + 1} - 1} \frac{1}{2^{2s}}\)
使用等比数列求和即可得到 \(\sum \limits _{i \ge 1} \frac{1}{i^2} \in \left[ \frac{1}{2}, 2\right]\)。
综上，\(\sum \limits _{i = 1} ^{n} \omega^2 (i) = \Theta (n \log^2 \log n)\)
\(D_n = \sum \limits _{i = 1} ^{n} \frac{\mu (i)}{i}\)
首先我们扔掉所有 \(4\) 的倍数。这部分答案是 \(0\)。
考虑设 \(m_i\) 表示 \(i\) 的最小质因子。
随后我们按照 \(m_i\) 是否为 \(2\) 对 \(i\) 进行分组。
\(D_n = \sum \limits _{m_i = 2} ^{n} \frac{\mu (i)}{i} + \sum \limits _{m_i \neq 2} ^{n} \frac{\mu (i)}{i}\)
对于 \(m_i = 2\) 的部分，我们不妨把质因子 \(2\) 除掉看看会发生什么。
\(D_n = \sum \limits _{m_i \neq 2} ^{n} \frac{\mu(i)}{i} - \sum \limits _{m_i \neq 2} ^{\frac{n}{2}} \frac{\mu i}{2i} = \frac{1}{2} D_{\frac{n}{2}} + \sum \limits _{i \ge \frac{n}{2}, m_i \neq 2} ^{n} \frac{\mu(i)}{i}\)
直接把后一项的 \(\frac{1}{i}\) 放缩成 \(\frac{2}{n}\) 即可，这一项就是 \(O(1)\) 的。
然后变成 \(D_n = \frac{1}{2} D_{\frac{n}{2}} + O(1)\)
最后得到 \(D_n = O(1)\)
什么，你问我为什么不卡下界了。
问就是不会。