基于同余定理和素筛的欧拉函数

在开始下面的欧拉函数学习之前，我希望各位大佬能够先熟练掌握素筛和基于同余定理的快速幂这两个算法，如果哪位大佬不太清楚这两个算法，可以先参考我博客中的《基于同余定理的快速幂》和《素数筛法》这两篇博客，熟悉之后，再来看这篇博客会有事半功倍的效果(๑• .* •๑)*

---

我们先说说欧拉函数是做什么的：

Euler函数：

欧拉函数是求小于x并且和x互质的数的个数（所谓两个数互质，那就是两个数的最大公约数是1）

通式：φ(x) = x ( 1 - 1/p1 )( 1 - 1/p2 )( 1 - 1/p3 )( 1 - 1/p4 )……( 1 - 1/pn )

*其中p1, p2……pn为x的所有不重合的质因数，x是不为0的整数（注意，我在这个地方加了一个不重合，比如 12 = 2 * 2 * 3 ，那么它的不重合的质因数就有 2 和 3，所以 φ(12) = x（1 - 1/2）( 1 - 1/3) = 4 ,也就是说 12 在 1~12 中有四个与其互质的数，分别为1、5、7、11，是不是2、3、4、6、8、9、10与12都不互质呢，很神奇吧 (ฅ>ω<ฅ)）

有个小细节是：φ(1)=1（唯一和1互质的数就是1本身）

---

下面就给大家讲一些原理证明和一些推论，比较枯燥，但是都有助于你欧拉函数的理解和学习๑•ั็ω•็ั๑）

欧拉函数是积性函数：
1.在微积分学领域，积性函数指的是具有 f( ab ) = f( a )f( b )特性的函数，而在数论领域中，这个概念略有不同（仅定义在正整数上），它揭示了整数的很多性质。

为了区分通常意义上的函数，我们定义算数函数（定义在所有正整数上的函数称为算数函数）：
在整个积性函数篇里，不加说明地，我们总是讨论算数函数。

定义1.1 算术函数 f （x）如果满足对于任意两个互质的正整数 m 和 n，均有f(mn) = f(m)f(n)，就称f（x）为积性函数（或乘性函数）。如果对于任意两个正整数 m 和 n ，均有f(mn) = f(m)f(n)，就称为完全积性函数。其实很容易找到一些积性函数，如f(n) = 1 , f(n) = n , f(n) = n^2，事实上所有的幂函数都是积性函数。
2.结合积性函数的定义和算数基本定理，很容易得到下面的定理：
定理2.1 如果f（x）是一个积性函数，对于任意的正整数 n 有素数幂分解n=( p1^a1 )*( p2^a2 )…( ps^as )，那么有f( n ) = f(p1^a1)f(p2a2)…f(ps^as)

所以说：设m与n是互素的正整数，那么f( mn ) = f( m )f( n )

---

OK通过前面的小引子，下面向您隆重推出今天的主角——欧拉函数（也被称为欧拉ϕ函数）
下面我们就来探讨欧拉函数在各个点上的取值。很容易得到对于素数p，ϕ( p ) = p − 1 ，那么反过来是不是也成立呢？

**定理1.1：**如果 p 是素数，那么ϕ( p ) = p − 1 .反之，如果p是正整数且满足ϕ( p ) = p − 1，那么p是一个素数。
证明：前句可由互质定义得到，我们只证明后句。若p不是素数，那么或是1或是合数。而ϕ( 1 ) = 1，但若 p 是合数，得有因子 0 < d < p0 < d < p ,而 p 不与自身互质，这使得和 p 互质的数至多只有p−2个，所以也不可能，故 p 是素数。
我们再进一步，看欧拉函数在素数的幂下的取值。实际上和素数幂 p^n 不互质的只有 p 的倍数，一共有p^n/p=p(n−1)个，故ϕ( p^n )=p^n−p( n−1 )。

定理1.2: 如果 p 是素数，那么ϕ(p^n) = p^n−p( n−1 )。

接下来我们讨论更一般的情况，为此，我们需要证明欧拉函数是一个积性函数。定理的证明依赖于同余的一些简单性质，由于本文是本系列的第一篇，所以这里尽量把需要用到的性质先给证一证。如果你对这些性质比较清楚，可以直接跳过下面的补充部分，直接进入定理的证明。

**定义1.3:**一个模 m 完全剩余系是一个整数的集合，使得任意整数恰和此集合中的一个元素模 m 同余。
引理1.3: m 个模 m 不同余的整数的集合构成一个模 m 的完全剩余系。
1.3.1剩余类的定义：
一个整数被正整数n除后，余数有n种情形：0，1，2，3，…，n-1，它们彼此对模n不同余。这表明，每个整数恰与这n个整数中某一个对模n同余。这样一来，按模n是否同余对整数集进行分类，
可以将整数集分成n个两两不相交的子集。我们把（所有）对模n同余的整数构成的一个集合叫做模n的一个剩余类
1.3.2完全剩余系的定义：
从模n的每个剩余类中各取一个数，得到一个由n个数组成的集合，叫做模 n ( 就是用 n 对某个数求余 )的一个完全剩余系
证明： 假设 m 个模 m 不同余的整数的集合不是一个模 m 的完全剩余系。那么可能存在整数 a，使得集合中存在不止一个元素和 a 同余，但由于同余的性质，如果 a 和 b 模 m 同余，且 a 和 c 模 m 同余，那么必有 b 和 c 模 m 同余，和假设不符；那么可能存在整数 a，使得集合中不存在元素和 a 同余，但模 m 的余数只有 m 种可能， a 否定了一种可能，意味着集合里的元素模 m 至多只有 m−1 个值，但集合中的 m 个元素互不同余，应有 m 个不同的值，和假设不符。故原假设成立。
由上述引理，容易得到 0 , 1 , 2 , 3 , … , m−1 是模 m 的一个完全剩余系。

**定理1.4：**当n为奇数时，有：ϕ(2n) = n，因为2n是偶数，偶数与偶数一定不互素，所以只考虑2n与小于它的奇数互素的情况，则恰好就等于n的欧拉函数值。但是你不能说

引理1.5： 若 r1 , r2 , … , rm 是模 m 的一个完全剩余系，且正整数 a 满足gcd( a,m ) = 1 ,则对任意整数b，ar * 1+b , ar * 2+b , … , ar * m+b 都是模 m 的完全剩余系。
证明：由引理1.3，我们只需证明这 m 个数互不同余。取任意两个元素 ri , rj , i≠j 相减，得a * ri+b−(a * rj+b)=a( ri − rj ) .
若我们有a * ri≡a * rj(mod m) , 基于同余的性质，在gcd(a,m)=1的情况下，两边可以约去 a，于是得到 ri≡rj(mod m)，这和假设矛盾，故a * ri 与 a * rj 不同余，故引理成立。

结合以上定理，以及算数基本定理，我们可以求得任意正整数的欧拉函数值：

定理1.6： 设n=（p1^a1）*（p2a2）…（pk^ak）为正整数 n 的素数幂分解，那么ϕ(n) = n( 1−1/p1 )( 1−1/p2 )…( 1−1/pk )
**注意：n = （p1^a1）*（p2a2）…（pk^ak） **
而：ϕ(pk^ak)=（pkak）−（pk^{ak−1）=（pk}ak）(1−1/pk)
**证明：**因为ϕ( n )=ϕ(p1^a1)ϕ(p2a2)…ϕ(pk^{ak),又因为ϕ(pk}ak)=（pk^{ak）−（pk}ak−1），于是有：
ϕ(n)=（p1^a1）*（p2a2）…（pk^ak）(1−1/p1)(1−1/p2)…(1−1/pk)=n(1−1/p1)(1−1/p2)…(1−1/pk)

所以计算单个欧拉函数值的过程实际上就是先对正整数 n 进行分解的过程，我们从2开始从小到大寻找 n 的因子，显然找到的最小的因子必是素数（如果是合数，那在这之前就应该能找到这个合数的因子，当然也是 n 因子，肯定也是素数），找到后把这个素因子全部约去，并计算(1−1/p1)，然后接着向前，由于之前的因子已经消去，我们仍能保证找到的因子是素数。

完整的代码如下：

#include<iostream>
#include<cmath>
using namespace std; 
//下面是欧拉函数的核心代码，在欧拉函数之前可以写素筛的函数，以便在欧拉函数的第一层循环中直接对素数遍历，非素数不用遍历 
int euler(int x){
	int res = x;
	for(int i = 2; i<(int)sqrt(x*1.0)+1;i++)	//该for循环中的判断语句，与素筛中第一层循环的处理方法相同，即根号n~n中的是由1~根号n中的数的倍数，或者是大于根号n的素数，比如n =  2 * 97 * 101 根号n肯定大于97,那101又如何取到呢？其实在for循环中把1~根号n的判断完后剩下的101会在下面的	if(x > 1) res = res /x * (x -1);中被处理，因为如果剩余的数大于1，那么肯定是大于根号n的素数，且只有这一个大于根号n的素数其余的大于根号n的数均为合数 
		if(x % i == 0){
			res = res / i * (i - 1);			//这步相当于res = res * (i - 1) / i 
				while(x % i == 0) x /= i;		//这一步就是所谓的将x中重合的相同质因子全部舍掉，因为欧拉函数通式中重合的质因子只需要一个 
		}
	if(x > 1) res = res /x * (x -1);
	return res;
}
int main()
{
	int n;
	while(cin>>n){
		cout<<euler(n)<<endl;
	}
	return 0;
}

上面的代码在判断很少的几个数的欧拉函数值的时候可以使用，那如果让你求出1~10000所有的数的欧拉函数值那该怎么办呢？
这个时候我们就要借助打表的思想，即像素筛那样将每个数的欧拉函数值存放到对应下标的数组中去，但是用递推法求欧拉函数的值有几点需要注意的地方，笔者已经在代码中注释了，还望读者耐心阅读，并自己动手去多调试调试：

#include<iostream>
#include<cmath>
using namespace std; 
int p[100010];
void phi(){
	for(int i = 1;i<100010;i++) p[i] = i;//假设刚开始每个数的欧拉函数值等于它本身，这一步操作为下面素数的判定打下了良好的基础 
	for(int i = 2;i<100010;i+=2) p[i] >>=1; //这个地方用到了定理1.4的知识点，将所有的偶数都除以2，而且用的位运算，那么有读者会说了，8和4的欧拉函数值怎么可能一样，其实这里除以2就相当于n(1-1/2),是不是相当于n/2 ? 因为偶数都有2这个质因子 ,所以索性直接除以2 
	for(int i = 3;i<100010;i+=2){
		if(p[i] == i){					//请看代码末
			for(int j = i;j<100010;j+=i) p[j] = p[j] - p[j]/i;//其实就是 p[j] = p[j]*(1-1/i)，这个地方不写成p[j] = p[j]*(1-1/i) 的原因是(1 - 1/i)会变成浮点数，使结果不精确 
		}
	} 
}
int main()
{
	phi(); 
	int n;
	while(cin>>n){
		cout<<p[n]<<endl;
	}
	return 0;
}
//因为解释太长我就注释到这了，代码中if(p[i] == i)这一步是用来判断 i 是不是素数，首先i肯定是奇数，然后如果p[i]依旧等于i,说明 p[i]在之前的循环中值没有改变，比如i = 3的时候，3的倍数所对应的下标的值都会计算p[3的倍数] = p[3的倍数]*(1 - 1/3),所以在循环到 i=9 时，p[9]的值已经被改变，所以没被改变的，都是除了1和它本身没有因子的，那么肯定是素数，有人可能想问i一直遍历奇数，那么偶数呢？偶数首先肯定不是素数，并且在下面第二层遍历的时候，读者应该能够发现当i = 3时，遍历到了j = 6，所以依旧进行了计算p[6] = p[6]*( 1 - 1/3),并且后面那个p[6]的值已经在前面除以2了，是不是很神奇啊 

大佬们不懂的地方要私信我呀(๑• . •๑)，喜欢就顶一下吧，嘻嘻(๑• . •๑)