🚧 博客系统即将搬迁，将集成到 skywt.cn/blog。欢迎体验！
📧 现在可以使用邮箱订阅本博客。欢迎订阅！

欧拉筛的应用：在线性时间（O(N)）内求出 1~N 的欧拉函数

之前学习了欧拉函数以及几个性质，知道了“欧拉函数 $\varphi(n)$ 是小于或等于 $n$ 的正整数中与 $n$ 互质的数的数目。”对于求解单个的 $\varphi(x)$ 很简单，直接枚举就可以了；但是如果要你在 $\Theta (N)$ 时间复杂度内求 $\varphi(i)$ 的值（$i=1,2,\dots,n$），怎么求呢？自然是用欧拉筛了～

More...

埃氏筛法（朴素筛法及其优化）与欧拉筛（线性筛法）略解

在之前我们学过的最朴素的筛法就是埃氏筛法（埃拉托斯特尼筛法），它的复杂度是 $\Theta (N \log_2(N))$。其实这个朴素的筛法可以进行常数上的优化。还有一种更炫酷的筛法：欧拉筛，即线性筛法，时间复杂度为 $\Theta (N)$。

More...

以 O(N) 线性时间复杂度递推逆元的方法

在之前我们已经知道乘法逆元的三种求法，对于一般的题目让你把答案模一个质数，如果要求逆元一般用费马小定理，可以在 $\Theta (Nlog_2(N))$ 时间内构造出 1 到 N 的逆元：$inv(x)=x^{mo-2} \bmod mo$。但是对于 $10^7$ 级别的 $N$，这样的求法就显得有点慢。能不能在 $\Theta (N)$ 时间内递推出 $inv(x)$ 呢？

More...

利用容斥原理求解 [a,b] 区间中与 n 互质的数字个数

先看这道~~丧心病狂的~~题目：HDU 4135 Co-prime。题目大意就是，有 $T$ 组询问，每组询问给你三个数：$a, b, c$，问你闭区间 $[a,b]$ 中有多少个数字与 $n$ 互质。数据范围是：$1 \leqslant A \leqslant B \leqslant 10^{15}$，$1 \leqslant N \leqslant 10^5$。

乍一看毫无头绪，仿佛怎么做都会超时……其实用容斥的想法就很容易了～

More...