数论 - SkyWT

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

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

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

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

欧拉函数 φ(n) 的几个常用性质

之前我们已经知道欧拉函数 $\varphi(n)$ 的计算公式：

\displaystyle \varphi (n)=n \ast \prod_{i-1}^{r} (\frac {p_i-1} {p_i})

我们还知道它的两条性质：
如果 $\varphi(x)$ 中的x是质数 p 的 k 次幂，那么 $\displaystyle \varphi (x)=\varphi (p^k)=(p-1)p^{k-1}$ ；
欧拉函数是积性函数，如果 x 和 y 互质，则 $\varphi(xy)=\varphi(x) \varphi(y)=(x-1)(y-1)$ 。

今天我们要证明上述性质，再介绍几条新的性质。