浅谈欧拉函数

矫情吗；* 2022-12-12 13:54 182阅读 0赞

## 前言 ##

欧拉函数听起来很高大上，但其实非常简单，也是NOIP里的一个基础知识，希望大家看完我的博客能有所理解。  
数论是数学的一个分支，它只讨论正整数的性质，所以以下都是针对正整数进行研究的。

## 什么是欧拉函数 ##

欧拉函数是小于x的整数中与x互质的数的个数，一般用φ(x)表示。特殊的，φ(1)=1。

## 如何计算欧拉函数 ##

通式： φ(x)=x ∏ i = 1 n ( 1 − 1 p i ) \\prod\_\{i=1\}^n\{(1-\\frac\{1\}\{p\_i\})\} ∏i=1n(1−pi1)  
φ(1)=1  
其中 p 1 p\_1 p1, p 2 p\_2 p2…… p n p\_n pn为x的所有质因数，x是正整数。  
那么，怎么理解这个公式呢？对于x的一个质因数 p i p\_i pi，因为x以内 p i p\_i pi的倍数是均匀分布的，所以x以内有 1 p i \\frac \{1\}\{p\_i\} pi1的数是 p i p\_i pi的倍数，那么有1- 1 p i \\frac \{1\}\{p\_i\} pi1的数不是 p i p\_i pi的倍数。再对于 p j p\_j pj，同理，有1- 1 p j \\frac \{1\}\{p\_j\} pj1的数不是 p j p\_j pj的倍数，所以有 ( 1 − 1 p i ) ∗ ( 1 − 1 p j ) (1-\\frac \{1\}\{p\_i\})*(1-\\frac \{1\}\{p\_j\}) (1−pi1)∗(1−pj1)的数既不是 p i p\_i pi的倍数，又不是 p j p\_j pj的倍数。最后就有 ∏ i = 1 n ( 1 − 1 p i ) \\prod\_\{i=1\}^n\{(1-\\frac\{1\}\{p\_i\})\} ∏i=1n(1−pi1)的数与x互质，个数自然就是x ∏ i = 1 n ( 1 − 1 p i ) \\prod\_\{i=1\}^n\{(1-\\frac\{1\}\{p\_i\})\} ∏i=1n(1−pi1)。  
还不理解？没关系，举个例子。比如x=12，12以内有 1 2 \\frac \{1\}\{2\} 21的数是2的倍数，那么有1- 1 2 \\frac \{1\}\{2\} 21的数不是2的倍数（1,3,5,7,9,11），这6个数里又有 1 3 \\frac \{1\}\{3\} 31的数是3的倍数，只剩下(1- 1 2 \\frac \{1\}\{2\} 21)* (1- 1 3 \\frac \{1\}\{3\} 31)的数既不是2的倍数，也不是3的倍数（1,5,7,11）。这样剩下的 12\*(1- 1 2 \\frac \{1\}\{2\} 21)\*(1- 1 3 \\frac \{1\}\{3\} 31)，即4个数与12互质，所以φ(12)=4。

## 积性函数 ##

先介绍一下什么是积性函数，后面将会用到。若当m与n互质时， f ( m ∗ n ) = f ( m ) ∗ f ( n ) f(m\*n)=f(m)*f(n) f(m∗n)=f(m)∗f(n)，那么f是积性函数。若对任意正整数，都有f(m*n)=f(m)\*f(n)成立，则f是完全积性函数。

## 欧拉函数的几个性质 ##

1.对于质数p， φ ( p ) = p − 1 φ§=p-1 φ§=p−1。  
2.若p为质数， n = p k n=p^k n=pk，则 φ ( n ) φ(n) φ(n)= p k p^k pk- p k − 1 p^\{k-1\} pk−1。  
3.欧拉函数是积性函数，但不是完全积性函数。若m,n互质，则 φ ( m ∗ n ) = φ ( m ) ∗ φ ( n ) φ(m\*n)=φ(m)*φ(n) φ(m∗n)=φ(m)∗φ(n)。特殊的，当m=2，n为奇数时，φ(2*n)=φ(n)。  
4.当n>2时，φ(n)是偶数。  
5.小于n的数中，与n互质的数的总和为：φ(n) \* n / 2 (n>1)。  
6. n = ∑ d ∣ n φ ( d ) n=\\sum\_\{d|n\}\{φ(d)\} n=∑d∣nφ(d)，即n的因数（包括1和它自己）的欧拉函数之和等于n。

## 欧拉函数性质的粗略证明 ##

1.因为p是质数，所以1到n-1都与n互质。  
2.n只有一个质因数p，根据公式φ(x)=x ∏ i = 1 n ( 1 − 1 p i ) = x ∗ ( 1 − 1 p ) = p k ∗ ( 1 − 1 p ) = p k − p k − 1 \\prod\_\{i=1\}^n\{(1-\\frac\{1\}\{p\_i\})\} =x\*(1-\\frac\{1\}\{p\})=pk\*(1-\\frac\{1\}\{p\})=pk-p^\{k-1\} ∏i=1n(1−pi1)=x∗(1−p1)=pk∗(1−p1)=pk−pk−1。  
3.因为m与n互质，所以它们没有公共的质因数。设m有 a m a\_m am个质因数，n有 a n a\_n an个质因数。 φ ( m ) ∗ φ ( n ) = m ∗ n ∗ ∏ i = 1 a m ( 1 − 1 p i ) ∗ ∏ i = 1 a n ( 1 − 1 p i ) = m ∗ n ∗ ∏ i = 1 a m + a n ( 1 − 1 p i ) = φ ( m ∗ n ) φ(m)\* φ(n)=m*n \* \\prod\_\{i=1\}\{a\_m\}\{(1-\\frac\{1\}\{p\_i\})\}\*\\prod\_\{i=1\}\{a\_n\}\{(1-\\frac\{1\}\{p\_i\})\}=m*n \* \\prod\_\{i=1\}^\{a\_m+a\_n\}\{(1-\\frac\{1\}\{p\_i\})\}=φ(m*n) φ(m)∗φ(n)=m∗n∗∏i=1am(1−pi1)∗∏i=1an(1−pi1)=m∗n∗∏i=1am+an(1−pi1)=φ(m∗n)。  
4.前几个都可以利用公式证明，这个却不行。首先有一个基本事实（我不想证明），若gcd(n,m)=1，则gcd(n,n-m)=1（设n>m)。当m=n-m时， n = 2 ∗ m n=2*m n=2∗m，那么n>2时gcd(n,m)<>2，与前提相悖，故m<>n-m。换句话说，n>2时，与n互质的数是成对出现的，所以φ(n)必为偶数。  
5.证明这个也要用到上面所说的基本事实。与n互质的数一个是m，那么还存在另一个数n-m也与n互质。所以与n互质的数的平均数是n/2，而个数又是φ(n)，可以得到这些数的和就是φ(n)*n/2。  
6.证明1（理性的证明）：  
这个证明起来有点麻烦。设F(n)= ∑ d ∣ n φ ( d ) \\sum\_\{d|n\}\{φ(d)\} ∑d∣nφ(d)。首先证明F(n)是个积性函数：设m，n互质，则要证 F ( m ∗ n ) = F ( m ) ∗ F ( n ) F(m*n)=F(m)*F(n) F(m∗n)=F(m)∗F(n)。 F ( m ) ∗ F ( n ) = ∑ i ∣ m φ ( i ) ∗ ∑ j ∣ n φ ( j ) = φ ( i 1 ) ∗ φ ( j 1 ) + φ ( i 1 ) ∗ φ ( j 2 ) + . . . + φ ( i 2 ) ∗ φ ( j 1 ) + φ ( i 2 ) ∗ φ ( j 2 ) + . . . + φ ( i k m ) ∗ φ ( j k n ) F(m)F(n)=\\sum\_\{i|m\}\{φ(i)\}\\sum\_\{j|n\}\{φ(j)\}=φ(i\_1)φ(j\_1)+φ(i\_1)φ(j\_2)+…+φ(i\_2)φ(j\_1)+φ(i\_2)φ(j\_2)+…+φ(i\_\{km\})φ(j\_\{kn\}) F(m)∗F(n)=∑i∣mφ(i)∗∑j∣nφ(j)=φ(i1)∗φ(j1)+φ(i1)∗φ(j2)+…+φ(i2)∗φ(j1)+φ(i2)∗φ(j2)+…+φ(ikm)∗φ(jkn)这里假设 i 1 , i 2 , . . . i k m i\_1,i\_2,…i\_\{km\} i1,i2,…ikm为m的所有因数， j 1 , j 2 , . . . j k n j\_1,j\_2,…j\_\{kn\} j1,j2,…jkn为n的所有因数之和，因为m与n互质，所以它们的因数也必然全都两两互质，而欧拉函数又是个积性函数，即 φ ( i k ∗ j k ) = φ ( i k ) ∗ φ ( j k ) φ(i\_kj\_k)=φ(i\_k)φ(j\_k) φ(ik∗jk)=φ(ik)∗φ(jk)，那么上式又可以等价于 φ ( i 1 ∗ j 1 ) + φ ( i 1 ∗ j 2 ) + . . . + φ ( i 2 ∗ j 1 ) + φ ( i 2 ∗ j 2 ) + . . . + φ ( i k m ∗ j k n ) 。 φ(i\_1j\_1)+φ(i\_1j\_2)+…+φ(i\_2j\_1)+φ(i\_2j\_2)+…+φ(i\_\{km\}j\_\{kn\})。 φ(i1∗j1)+φ(i1∗j2)+…+φ(i2∗j1)+φ(i2∗j2)+…+φ(ikm∗jkn)。可以发现， i 1 ∗ j 1 , i 1 ∗ j 2 , . . . , i 2 ∗ j 1 , i 2 ∗ j 2 , . . . , i k m ∗ j k n i\_1j\_1,i\_1j\_2,…,i\_2*j\_1,i\_2*j\_2,…,i\_\{km\}j\_\{kn\} i1∗j1,i1∗j2,…,i2∗j1,i2∗j2,…,ikm∗jkn这些数构成了 m ∗ n mn m∗n的所有因数。那么这些数的欧拉函数之和就等于 F ( m ∗ n ) F(m*n) F(m∗n)，所以 F ( m ∗ n ) = F ( m ) ∗ F ( n ) F(m\*n)=F(m)\*F(n) F(m∗n)=F(m)∗F(n)，证得F是一个积性函数。根据这个性质，F可以一直分解到n为质数的幂的情况。那么讨论当p为质数时，F(p^k)怎么计算。因为 p k p^k pk的因数只有 1 , p , p 2 , p 3 , . . . , p k 1,p,p2,p3,…,p^k 1,p,p2,p3,…,pk，根据F的定义，直接展开来计算就行了。（根据欧拉函数的性质2，φ( p k p^k pk)= p k − p ( k − 1 ) pk-p(k-1) pk−p(k−1)） F ( p k ) = φ ( 1 ) + φ ( p ) + φ ( p 2 ) + . . . + φ ( p k ) = 1 + ( p − 1 ) + ( p 2 − p ) + . . . + ( p k − p ( k − 1 ) ) = p k 。 F(pk)=φ(1)+φ§+φ(p2)+…+φ(pk)=1+(p-1)+(p2-p)+…+(pk-p(k-1))=p^k。 F(pk)=φ(1)+φ§+φ(p2)+…+φ(pk)=1+(p−1)+(p2−p)+…+(pk−p(k−1))=pk。既然对于质数的幂，F(n)=n成立，而F又是个积性函数，这个结论就可以扩展到任意正整数了。至此，命题得证。  
证明2（感性的证明）：  
以12为例。12的因子有1,2,3,4,6,12。把与这些数互质的数列出来：  
1:1  
2:1  
3:1 2  
4:1 3  
6:1 5  
12 1 5 7 11  
不妨把这些数作为分母，把与这些数互质的数作为分子，写成分数形式：  
1/1  
1/2  
1/3 2/3  
1/4 3/4  
1/6 5/6  
1/12 5/12 7/12 11/12  
显然，每一行的数的个数就是该行的分母的欧拉函数值。倘若把这些数都改成以12为分母的数：  
12/12  
6/12  
4/12 8/12  
3/12 9/12  
2/12 10/12  
1/12 5/12 7/12 11/12  
可以发现，这些数是以12为分母，1~12为分子的所有数，所以个数为12个。所以与12互质的数的欧拉函数值之和就是12。这样，命题大概就被证明了吧。

## 求欧拉函数 ##

**埃拉托斯特尼筛求欧拉函数**

观察欧拉函数的公式，φ(x)=x ∏ i = 1 n ( 1 − 1 p i ) \\prod\_\{i=1\}^n\{(1-\\frac\{1\}\{p\_i\})\} ∏i=1n(1−pi1) = x ∏ i = 1 n p i − 1 p i \\prod\_\{i=1\}^n\{\\frac\{p\_i-1\}\{p\_i\}\} ∏i=1npipi−1 。我们用phi\[x\]表示φ(x)。可以一开始把phi\[x\]赋值为x，然后每次找到它的质因数就 p h i \[ x \] = p h i \[ x \] / p i ∗ ( p i − 1 ) phi\[x\]=phi\[x\]/p\_i\*(p\_i-1) phi\[x\]=phi\[x\]/pi∗(pi−1)（先除再乘，避免溢出）。当然，若只要求一个数的欧拉函数，可以从1到sqrt(n)扫一遍，若gcd(i,n)=1就更新 p h i \[ n \] phi\[n\] phi\[n\]。复杂度为O(logn)（代码就不给了）。那要求1~n所有数的欧拉函数呢？可以用埃拉托斯特尼筛的思想，每次找到一个质数，就把它的倍数更新掉。这个复杂度虽然不是O(n)，但还是挺快的（据说是O(n\*ln ln n)，关于证明，可以点这里，虽然我看不懂）。  
代码如下：

void euler(int n)
    { 
        for (int i=1;i<=n;i++) phi[i]=i;
        for (int i=2;i<=n;i++)
        { 
            if (phi[i]==i)//这代表i是质数
            { 
                for (int j=i;j<=n;j+=i)
                { 
                    phi[j]=phi[j]/i*(i-1);//把i的倍数更新掉
                }
            }
        }
    }

**欧拉筛求欧拉函数**

前提是要懂欧拉筛。每个数被最小的因子筛掉的同时，再进行判断。i表示当前做到的这个数，prime\[j\]表示当前做到的质数，那要被筛掉的合数就是i\*prime\[j\]。若prime\[j\]在这个合数里只出现一次（i%prime\[j\]!=0），也就是i和prime\[j\]互质时，则根据欧拉函数的积性函数的性质，phi\[i \* prime\[j\]\]=phi\[i\] \* phi\[prime\[j\]\]。若prime\[j\]在这个合数里出现了不止一次（i%prime\[j\]=0），也就是这个合数的所有质因子都在i里出现过，那么根据公式，φ(i \* prime\[j\])=prime\[j\] \* i \* ∏ k = 1 n ( 1 − 1 p k ) \\prod\_\{k=1\}^n\{(1-\\frac\{1\}\{p\_k\})\} ∏k=1n(1−pk1) =φ(i) \*prime\[j\]。复杂度为O(n)。  
还是看代码吧：

void euler(int n)
    { 
    	phi[1]=1;//1要特判 
    	for (int i=2;i<=n;i++)
    	{ 
    		if (flag[i]==0)//这代表i是质数 
    		{ 
    			prime[++num]=i;
    			phi[i]=i-1;
    		}
    		for (int j=1;j<=num&&prime[j]*i<=n;j++)//经典的欧拉筛写法 
    		{ 
    			flag[i*prime[j]]=1;//先把这个合数标记掉 
    			if (i%prime[j]==0)
    			{ 
    				phi[i*prime[j]]=phi[i]*prime[j];//若prime[j]是i的质因子，则根据计算公式，i已经包括i*prime[j]的所有质因子 
    				break;//经典欧拉筛的核心语句，这样能保证每个数只会被自己最小的因子筛掉一次 
    			}
    			else phi[i*prime[j]]=phi[i]*phi[prime[j]];//利用了欧拉函数是个积性函数的性质 
    		}
    	}
    }

## 总结 ##

有关欧拉函数的性质，只需做个了解，而求欧拉函数的代码，却是一定要会写的。这只是走进数论世界的第一步。  
转自：https://blog.csdn.net/liuzibujian/article/details/81086324?utm\_medium=distribute.pc\_relevant.none-task-blog-OPENSEARCH-1&depth\_1-utm\_source=distribute.pc\_relevant.none-task-blog-OPENSEARCH-1