算法总结之欧拉函数&中国剩余定理

1.欧拉函数

　　概念：在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。

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

　　　　其中p1, p2……pn为x的所有质因数，x是不为0的整数 

　　注意：

　　　　1) φ(1)=1.

　　　　2)每种质因数只一个。比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4

　　　　3)若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。

　　　　4)φ(mn)=φ(m)φ(n)

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

　　代码实现：

1)直接求欧拉数：

1 /*函数返回值为n的欧拉函数值*/ 2 int euler(int n) 3 { 4     int s=n,i,m; 5     m=sqrt(n); 6     for(i=2;i<=m;i++){ 7         if(n%i==0) 8             s=s/i*(i-1); 9         while(n%i==0)10             n/=i;11     }12     if(n>1)13         s=s/n*(n-1);14     return s;15 }

2)打表

1 /*打印1-MAXN的欧拉函数表*/ 2 int a[MAXN]= {
   1,1,0}; 3 void euler() 4 { 5     int i,j; 6     for(i=2; i<=MAXN; i++) 7         if(!a[i]) 8             for(j=i; j<=MAXN; j+=i) 9             {10                 if(a[j]==0) a[j]=j;11                 a[j]=a[j]/i*(i-1);12             }13 }

 2.中国剩余定理

　　原文：

　　　　《孙子算经》中的题目：有物不知其数，三个一数余二，五个一数余三，七个一数又余二，问该物总数几何？

　　　　《孙子算经》中的解法：三三数之，取数七十，与余数二相乘；五五数之，取数二十一，与余数三相乘；七七数之，取数十五，与余数二相乘。将诸乘积相加，然后减去一百零五的倍数。

　　结论：

　　　　令任意固定整数为M，当M/A余a，M/B余b，M/C余c，M/D余d，…，M/Z余z时，这里的A，B，C，D，…，Z为除数，除数为任意自然数时；余数a，b，c，d，……，z为自然整数时。

　　　　1)当命题正确时，在这些除数的最小公倍数内有解，有唯一的解，每一个最小公倍数内都有唯一的解。

　　　　2)当M在两个或两个以上的除数的最小公倍数内时，这两个或两个以上的除数和余数可以定位M在最小公倍数内的具体位置，也就是M的大小。

　　　　3)正确的命题：分别除以A，B，C，D，…，Z不同的余数组合个数=A，B，C，D，…，Z的最小公倍数=不同的余数组合的循环周期。

　　具体步骤(以《孙子算经》中的题目为例):

　　　　1)找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70。

　　　　2)用15乘以2(2为最终结果除以7的余数)，用21乘以3(3为最终结果除以5的余数)，同理，用70乘以2(2为最终结果除以3的余数)，然后把三个乘积相加(15*2+21*3+70*2)得到和233。

　　　　3)用233除以3，5，7三个数的最小公倍数105，得到余数23，即233%105=23。这个余数23就是符合条件的最小数。