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

时间:2022-11-04 05:15:06

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

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)直接求欧拉数:

 /*函数返回值为n的欧拉函数值*/
int euler(int n)
{
int s=n,i,m;
m=sqrt(n);
for(i=;i<=m;i++){
if(n%i==)
s=s/i*(i-);
while(n%i==)
n/=i;
}
if(n>)
s=s/n*(n-);
return s;
}

2)打表

 /*打印1-MAXN的欧拉函数表*/
int a[MAXN]= {,,};
void euler()
{
int i,j;
for(i=; i<=MAXN; i++)
if(!a[i])
for(j=i; j<=MAXN; j+=i)
{
if(a[j]==) a[j]=j;
a[j]=a[j]/i*(i-);
}
}

 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就是符合条件的最小数。