欧拉函数精品课件.pptVIP

欧拉函数

Eulerstotientfunctionφ函数欧拉商数*Define定义在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数、欧拉商数等。例如φ(8)=4，因为1,3,5,7均和8互质。φ(7)=6,因为1,2,3,4,5,6,7均和7互质。特别的，φ(1)=1一般的，若k为质数(素数)，则φ(k)=k-1若k为合数，则有不等式φ(k)=k-sqrt(k)*Derivation推导对于一个合数n，若其满足n为素数p的k次幂，即n=p^k因为除了p的倍数外，其余数都和n互质φ(n)=φ(p^k)=p^k-p^(k-1)=(p-1)p^(k-1)FundamentalRules!!!!!!!!!!*Quote引入积性函数在非数论的领域，积性函数指所有对于任何a,b都有性质f(ab)=f(a)f(b)的函数。数论中的积性函数，对于正整数n的一个算术函数f(n)，当中f(1)=1且当a,b互质，f(ab)=f(a)f(b)，在数论上就称它为积性函数。若某算术函数f(n)符合f(1)=1，且就算a,b不互质，f(ab)=f(a)f(b)，则称它为完全积性的。那么，欧拉函数是否也是一个积性函数？既然我这么问。答案是肯定的。。。。O(︶︿︶)o那么，证明？*Proof证明123…k…bb+1b+2b+3…b+k…2b2b+12b+22b+3…2b+k…3b3b+13b+23b+3…3b+k…4b…(a-1)b+1(a-1)b+2(a-1)b+3…(a-1)b+k…ab考虑右边这样一个a*b的矩阵，(a,b)互质。在一行中有φ(b)与b互质，其余不与b互质删去，留下φ(b)列因为0,1,2,…...,a-1构成一个moda的完系又因为a,b互质则有0*b+k,1*b+k,2*b+k,…….,(a-1)*b+k亦为moda的完系其中有φ(a)个与a互质得到φ(a)*φ(b)=φ(a*b)得证!!!!!!!!!*Conclude归纳*Extend扩展*Summarize总结欧拉函数是一个解决组合及方案数的一种方法其中构造欧拉函数数组，最快可以用O(NlogN)的时间复杂度达成~是一种高效的解体方法局限性当然也有，这类题普遍难以想到用欧拉函数的思想，代码实现还是轻松轻松愉悦愉悦的~*Code代码实现voidGet_Eular(){for(inti=1;i=range;i++){eular[i]=1;prime[i]=1;}//初始化，假设每个数都是素数，欧拉函数值为1for(inti=2;i=range;i++){if(prime[i]){p[++num]=i;eular[i]=i-1;}//如果i是素数，p记录有哪些素数for(intj=1;j=num;j++){if(p[j]*irange)break;//超出范围，退出prime[i*p[j]]=0;//显然不是素数了if(i%p[j]==0){eular[i*p[j]]=eular[i]*p[j];break;}//i,p[j]不互质elseeular[i*p[j]]=eular[i]*(p[j]-1);}}}//O(NlogN)*Properties性质欧拉定理EulerTheorem欧拉定理实际上是费马小定理的推广。此外还有平面几何中的欧拉定理、多面体欧拉定理(在一凸多面体中，顶点数-棱边数+面数=2)。西方经济学中欧拉定理又称为产量分配净尽定理，指在完全竞争的条件下，假设长期中规模收益不变，则全部产品正好足够分配给各个要素。另有欧拉公式。费马小定理假如p是质数，且(a,p)=1，那么a^(p-1)≡1（modp）假如p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1欧拉定理若n,a为正整数，且n,a互质，(a,n)=1，则a^φ(n)≡1(modn)。欧拉定理性质若n=1,则如果i整除n，则φ(i)的和=n。*Exercise练习POJ2478FareySeq