欧拉函数 学习笔记

基础印象

\(φ(n)\) ，多么小巧的符号！它就是欧拉函数(Euler's totient function)，表示小于等于n的、与n互质的数字的个数。

比如\(φ(1)=1,φ(5)=2,φ(12)=4\)…

具体解释来，12与1、5、7、11互质，\(φ(12)=4\)

注意：1与任何数互质，包括自己

开始烦人的推导了

那么显然地:

• 当n为质数时 \(φ(n)=n-1\)

接下来，如果 \(n=p^k\) ，那么 \((0,p)\) 和 \((p,2p)\) 和 \((2p,3p)\) …这些区间都与n互质。每个区间包含 \(p-1\)个数字,共 \(p^{k-1}\) 个区间，所以：

• 当 \(n=p^k\) 时， \(φ(n)=p^{k-1}*(p-1)\)

欧拉函数是积性函数( 即a与b互质时，\(φ(a)*φ(b)=φ(a*b)\) ),所以对于

\(n=a*b*c*d*…\)时，\(φ(n)=φ(a)*φ(b)*φ(c)*φ(d)*...\)

推一推式子即可扩展到一般情况：

• 当 \(n=p_1^{k_1}*p_2^{k_2}*p_3^{k_3}*…*p_m^{k_m}*\)时，即\(n=\prod^m_{i=1}p^{k_i}_i\)时，有$$φ(n)=n*\prod^m_{i=1}{\dfrac{p_i-1}{p_i}}$$

欧拉函数其它性质

• 当n为奇数时，\(φ(n)=φ(2n)\)

• \(n=\sum_{d|n}φ(d)\) 即 \(n=φ(它的一个因子)+φ(它的另一个因子)+...\)

• 如果\(n=p^k\)且p为质数，则\(φ(n)=p^k-p^{k-1}\)（比如\(16=2^4\),那么不互质的有2、4、6、8、10、12、14、16，共\(n/p\)个,所以\(φ(n)=n-n/p=p^k-p^{k-1}\)

• 若n与m互质，则\(n^{φ(m)}\equiv 1 \pmod {m}\)

• 上面那条可以扩展：\(a^{b} \equiv\left\{\begin{array}{ll} a^{b \bmod \varphi(p)}, & \operatorname{gcd}(a, p)=1 \\ a^{b}, & \operatorname{gcd}(a, p) \neq 1, b<\varphi(p) \quad(\bmod\, p) \\ a^{b \bmod \varphi(p)+\varphi(p)}, & \operatorname{gcd}(a, p) \neq 1, b \geq \varphi(p) \end{array}\right.\)

求欧拉函数

实现-求出一个数的欧拉函数:

1. 暴力枚举 \(1 \sim \sqrt{n}\)，然后判断 i和n 的 gcd是否为1。Time: \(O(logn \sqrt{n})\)
2. 枚举n的质因数，然后用上面的公式求得。代码实现如下。Time: \(O(logn)\)

lon phi(lon z){
	lon sqr=sqrt(z),tot=z;
	rep(i,2,sqr){
		if(z%i)continue;
		tot=tot/i*(i-1);
		while(z%i==0)z=z/i;
	}
	return tot;
}

if(z>1)tot=tot/z*(z-1); 指的是如果z大于1，证明还有一个质数没有处理（如果是两个质数，那么sqr肯定会大于小的那个，然后它就被处理），然后处理就行了。

实现-求出 \(1 \sim \sqrt{n}\) 的所有欧拉函数值

1. 打表 Time: \(O(1)\) （啊这
2. 因为有 \(φ(n)=n*\prod^m_{i=1}{\dfrac{p_i-1}{p_i}}\) ,所以反过来，对于每一个p，我们将p的倍数乘上\(\dfrac{p-1}p\)， 代码实现如下。Time: \(O(n)\)

void do_phi(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(phi[i])continue;
        for(int j=i;j<=n;j=j+i){
  	        if(!phi[j])phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
    }
}