标签：right frac log 19 闲话 sum 24.10 Theta left

闲话

今日推歌：毕业Graduate by 天使盐Tenshien feat. 诗岸
希望大家幸福。

那些你不要的：渐进一例

刚过去的 STAOI R8 T5，很多人用暴力直接草了过去。那么，复杂度真的有保障吗？

令 \(V = \max n \in \Theta(n)\)，\(A = \mathbb P \cap [1, V]\)。那么枚举 \(i\)，枚举 \(j = n \bmod i\)，再枚举每个符合条件的 \(n\)，总时间复杂度即

\[\begin{aligned} & \Theta\left(\sum_{i \in A} \sum_{j \in A, j < i} \frac{V - j}{i} \right) \\ = \ & \Theta\left(\sum_{i \in A} \left( \frac{V}{i} \frac{i}{\log i} - \frac{1}{i} \sum_{j \in A, j < i} j \right) \right) \\ = \ & \Theta\left( V\sum_{i \in A} \frac{1}{\log i} - \sum_{i \in A} \frac{1}{i} \sum_{j \in A, j < i} j \right) \\ = \ & \Theta\left( V \int_2^V \frac{1}{\log x} \mathrm d \pi(x) - \sum_{i \in A} \frac{1}{i} \int_2^i x \mathrm d \pi(x) \right) \\ = \ & \Theta\left( V \left( \frac{V}{\log^2 V} - \int_2^V \pi(x) \mathrm d\left(\frac{1}{\log x}\right) \right) - \sum_{i \in A} \frac{1}{i} \left(\frac{i^2}{\log i} - \int_2^i \pi(x) \mathrm d x \right) \right) \\ = \ & \Theta\left(V \left( \frac{V}{\log^2 V} + \int_2^V \frac{1}{\log^3 x} \mathrm dx \right) - \sum_{i \in A} \frac{1}{i} \left(\frac{i^2}{\log i} - \int_2^i \frac{x}{\log x} \mathrm d x \right) \right) \\ = \ & \Theta\left(\frac{V^2}{\log^2 V} + V\left(\frac{1}{2} \left(\text{li}(V)-\frac{V (\log (V)+1)}{\log ^2(V)}\right)\right) - \sum_{i \in A} \frac{1}{i} \left(\frac{i^2}{\log i} + \mathrm{Ei}(2\log i) \right) \right) \end{aligned} \]

由于 \(\mathrm{Ei}(\log x) = \mathrm{li}(x) \sim \dfrac{x}{\log x}\)，后半部分即

\[\begin{aligned} & \Theta\left(\sum_{i \in A} \frac{i}{\log i} \right) \\ = \ & \Theta\left(\int_2^V \frac{x}{\log x} \mathrm d \pi(x) \right) \\ = \ & \Theta\left(\frac{V^2}{\log^2 V} - \int_2^V \frac{x}{\log x} \left(\frac{1}{\log x} - \frac{1}{\log^2 x}\right)\mathrm dx \right) \\ = \ & \Theta\left(\frac{V^2}{\log^2 V} - \frac{V^2}{\log ^2(V)} \right) \end{aligned} \]

后半部分渐进趋于 \(0\)。那么原式即

\[\begin{aligned} = \ &\Theta\left(\frac{V^2}{\log^2 V} + V\left(\frac{1}{2} \left(\frac{V}{\log V} -\frac{V}{\log(V)} -\frac{V}{\log^2 V}\right)\right) \right) \\ = \ & \Theta\left(\frac{V^2}{\log^2 V}\right) \end{aligned} \]

最后同阶部分的消去是在 \(V\to\infty\) 的时候考察了一下系数。这是由于，当 \(V\to\infty\) 的时候，随着求和中分段数的增加，求和与积分的差值会无限减小，所以系数可以看作 \(1\)。那么毛估估一下就是对的了。

如果有更严谨的证明欢迎评论区 d 我，如果有问题也是 /cy

标签：right,frac,log,19,闲话,sum,24.10,Theta,left
From： https://www.cnblogs.com/joke3579/p/-/chitchat241019