欧拉筛的应用:在线性时间(O(N))内求出 1~N 的欧拉函数
之前学习了欧拉函数以及几个性质,知道了“欧拉函数 \varphi(n) 是小于或等于 n 的正整数中与 n 互质的数的数目。”对于求解单个的 \varphi(x) 很简单,直接枚举就可以了;但是如果要你在 \Theta (N) 时间复杂度内求 \varphi(i) 的值(i=1,2,\dots,n),怎么求呢?自然是用欧拉筛了~
之前学习了欧拉函数以及几个性质,知道了“欧拉函数 \varphi(n) 是小于或等于 n 的正整数中与 n 互质的数的数目。”对于求解单个的 \varphi(x) 很简单,直接枚举就可以了;但是如果要你在 \Theta (N) 时间复杂度内求 \varphi(i) 的值(i=1,2,\dots,n),怎么求呢?自然是用欧拉筛了~
在之前我们已经知道乘法逆元的三种求法,对于一般的题目让你把答案模一个质数,如果要求逆元一般用费马小定理,可以在 \Theta (Nlog_2(N)) 时间内构造出 1 到 N 的逆元:inv(x)=x^{mo-2} \bmod mo。但是对于 10^7 级别的 N,这样的求法就显得有点慢。能不能在 \Theta (N) 时间内递推出 inv(x) 呢?
之前我们已经知道欧拉函数 \varphi(n) 的计算公式:
我们还知道它的两条性质:
如果\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) 。
今天我们要证明上述性质,再介绍几条新的性质。