经过两天的努力 终于把AC大神的课件都看完了 感动啊啊啊TAT 顿时感觉智力上升了一个层次 之后看到数论的题目终于可以不用放弃治疗了~~~ 我会说我刚刚用了十分钟就把欧拉函数看完了吗~~~（其实之前就会-。-）
欧拉函数也就是phi(n) 表示小于等于n的且与n互质的数的个数
欧拉函数的公式是 phi(n)=n*(1-1/p1)*(1-1/p2)*...*(1-1/pn)
要证明这个公式 我们需要先证明一些简单的性质
1.若p为素数 phi(p)=p-1
小于某个素数的数都和这个素数互质- - 显然
2.phi(p^k)=(p-1)*p^(k-1)
小于等于p^k的数中不与p互质的数肯定都是p的倍数
这些数有p^k/p=p^(k-1)个 而总共有p^k个数
所以phi(p^k)=p^k-p(k-1)=(p-1)*p^(k-1)
3.若(a,b)=1 phi(a*b)=phi(a)*phi(b)
AC大神因为欧拉函数是积性函数0 0？ 我也不懂为什么- -...
4.若p|a 则phi(p*a)=phi(a)*p
设 a=a'*p^k ((a',p)=1)
phi(p^k)*p
=(p-1)*p^(k-1)*p
=(p-1)*p^k
=phi(p^(k+1))
phi(a)*p
=phi(a')*phi(p^k)*p
=phi(a')*phi(p^(k+1))
=phi(a*p)
综上所述
phi(n)
=phi(p1^a1*p2^a2*...*pn^an)
=phi(p1^a1)*phi(p2^a2)*...*phi(pn^an)
=((p1-1)*p1^(a1-1))*((p2-1)*p2^(a2-1))*...*((pn-1)*pn^(an-1))
=(p1^a1*p2^a2*...*pn^an)*((p1-1)*(p2-1)*...*(pn-1))/(p1*p2*...*pn)
=n*(1-1/p1)*(1-1/p2)*...*(1-1/pn)
得证！
顺便扯些关于欧拉函数的东西- -
欧拉定理：
若(a,n)=1 a^phi(n)=1(mod n)
费马小定理：
当n为质数且(a,n)=1时 a^(n-1)=1(mod n)
费马小定理推论：
这时a的乘法逆元为a^(n-2)
O(n)求欧拉函数代码：
1 void makepri(){ 2 for (ll i=2;i<=N;i++){ 3 if (!bo[i]){ 4 pri[++pri[0]]=i; 5 phi[i]=i-1; 6 } 7 for (ll j=1;j<=pri[0] && i*pri[j]<=N;j++){ 8 bo[i*pri[j]]=1; 9 if (i%pri[j]) phi[i*pri[j]]=phi[i]*(pri[j]-1); 10 else{ 11 phi[i*pri[j]]=phi[i]*pri[j]; 12 break; 13 } 14 } 15 } 16 } View Code
转载于:https://www.cnblogs.com/g-word/p/3375291.html
