其实我原来是把欧拉函数和欧拉定理写在一篇博客里的,但是后来发现欧拉函数特别常用,然后总去那里找也不方便,于是就把它单独分出来了。
**欧拉函数 $\varphi(n)$:**对于正整数 $n$,欧拉函数是不大于 $n$ 的正整数中与 $n$ 互质的数的数目。
通式:$\varphi(n)=x\prod_{i=1}^n\left(1-\frac{1}{p_i}\right)$,其中 $p_1,p_2,\cdots,p_n$ 为 $x$ 的所有质因子,$x$ 是不为 $0$ 的整数,$\varphi(1)=1$。
注意:只取不同的质因数。例如 $12=2\times 2\times 3$,那么 $\varphi(12)=12\times (1-\frac{1}{2})\times (1-\frac{1}{3})=4$。
欧拉函数的一些性质:
若 $n=p^k$,$p$ 为质数,$\varphi(n)=pk-p{k-1}=(p-1)p^{k-1}$;
若 $m,n$ 互质,$\varphi(mn)=\varphi(m)\varphi(n)$;
若 $n$ 为奇数,$\varphi(2n)=\varphi(n)$;
若 $n$ 为质数,$\varphi(n)=n-1$,此时的欧拉定理即为费马小定理。
算法实现与分析:
求解 $\varphi(n)$ 需要对 $n$ 进行素因子分解。
(1) 直接实现:
1 | int phi(int n) |
由分析知,这个函数的复杂度为 $O(n)$,如果 $n$ 达到 1 000 000 000,肯定会超时。
由于任何一个合数都至少有一个不大于 $\sqrt{n}$ 的素因子,所以只需要遍历到 $\sqrt{n}$ 即可,这样复杂度降低为 $O(\sqrt{n})$。
下面是优化代码:
1 | int phi(int n) |
(2) 素数表实现:
先把 50 000 以内的素数用筛法选出来并保存,以方便欧拉函数使用,这里采用埃拉托斯尼斯筛法。
这样,若不考虑筛法的时间复杂度,而单纯看欧拉函数,其复杂度变为 $O(x)$,$x$ 为 $\sqrt{n}$ 以内素数的个数。
1 | const int N = 50001; |
(3) 递推求欧拉函数:
如果频繁地要使用欧拉函数值,就需要预先打表。下面介绍递推求欧拉函数的方法。
可预先置所有数的欧拉函数值都为它本身,如果 $p$ 是一个正整数且满足 $\varphi§=p-1$,那么 $p$ 是素数,在遍历过程中如果遇到欧拉函数与自身相等的情况,那么说明该数为素数,把这个数的欧拉函数值改变,同时也把能被该素因子整除的数改变。其复杂度约为 $O(n\ln n)$。
1 | for (int i = 1; i <= maxn; ++i) |
maxn 是待求欧拉函数值的数的最大值,phi 数组存储欧拉函数值。