广东网站推广策略,华夏运用网站,网站开发视频压缩上传,潍坊手机网站建设算法总结之欧拉函数中国剩余定理 1.欧拉函数 概念#xff1a;在数论#xff0c;对正整数n#xff0c;欧拉函数是少于或等于n的数中与n互质的数的数目。 通式#xff1a;φ(x)x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn) 其中p1, p2……pn为x的所有质因数#xf… 算法总结之欧拉函数中国剩余定理 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)每种质因数只一个。比如122*2*3那么φ1212*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 sn,i,m;5 msqrt(n);6 for(i2;im;i){7 if(n%i0)8 ss/i*(i-1);9 while(n%i0)
10 n/i;
11 }
12 if(n1)
13 ss/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(i2; iMAXN; i)7 if(!a[i])8 for(ji; jMAXN; ji)9 {
10 if(a[j]0) a[j]j;
11 a[j]a[j]/i*(i-1);
12 }
13 } 2.中国剩余定理 原文 《孙子算经》中的题目有物不知其数三个一数余二五个一数余三七个一数又余二问该物总数几何 《孙子算经》中的解法三三数之取数七十与余数二相乘五五数之取数二十一与余数三相乘七七数之取数十五与余数二相乘。将诸乘积相加然后减去一百零五的倍数。 结论 令任意固定整数为M当M/A余aM/B余bM/C余cM/D余d…M/Z余z时这里的ABCD…Z为除数除数为任意自然数时余数abcd……z为自然整数时。 1)当命题正确时在这些除数的最小公倍数内有解有唯一的解每一个最小公倍数内都有唯一的解。 2)当M在两个或两个以上的除数的最小公倍数内时这两个或两个以上的除数和余数可以定位M在最小公倍数内的具体位置也就是M的大小。 3)正确的命题分别除以ABCD…Z不同的余数组合个数ABCD…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*221*370*2)得到和233。 3)用233除以357三个数的最小公倍数105得到余数23即233%10523。这个余数23就是符合条件的最小数。 转载于:https://www.cnblogs.com/Enumz/p/3878509.html
