线性筛与积性函数
线性筛是一种数论筛法,可以筛出一定范围内的质数或任意积性函数的值。
其中”线性“的含义为 每个数字只被其最小的质因数筛出 ,并非时间复杂度。
假设求积性函数 $f(x)$ 的质数幂 $f(p^k)$ 复杂度为 $t$,则最终复杂度为 $ \mathcal O(n+\frac{n}{\ln n}\times t)$ 。
NexT 主题优化
简单记录一下优化 NexT 主题过程中的一些细节。
There is a negligible beginning in all great action and thought.