欧拉函数
发布时间：2020-12-13 20:45:26 所属栏目：PHP教程 来源：网络整理
导读：先来介绍几个与欧拉函数有关的定理： 定理1：设m与n是互素的正整数，那末 定理2：当n为奇数时，有 。 由于2n是偶数，偶数与偶数1定不互素，所以只斟酌2n与小于它的奇数互素的情况，则恰好就等于n的欧拉函数。 定理3：设p是素数，a是1个正整数，那末 关于这个
|
先来介绍几个与欧拉函数有关的定理：
定理1：设m与n是互素的正整数，那末
定理2：当n为奇数时，有
由于2n是偶数，偶数与偶数1定不互素，所以只斟酌2n与小于它的奇数互素的情况，则恰好就等于n的欧拉函数值。
定理3：设p是素数，a是1个正整数，那末
关于这个定理的证明用到容斥：
由于
那末小于
定理4：设
这个定理可以根据定理1和定理3证明，其实用到的就是容斥。如果对容斥熟习，其实完全就能够直接容斥。
定理5：设n是1个正整数，那末
这个其实可以看莫比乌斯反演就明白了。
定理6：设m是正整数，(a,m)=1，则：
定理7：如果n大于2，那末n的欧拉函数值是偶数。
求欧拉函数值：
int phi(int n)
{
int i,rea=n;
for(i=2;i*i<=n;i++)
{
if(n%i==0)
{
rea=rea-rea/i;
while(n%i==0) n/=i;
}
}
if(n>1)
rea=rea-rea/n;
return rea;
}
利用递推法求欧拉函数值：
算法原理：开始令i的欧拉函数值等于它本身，如果i为偶数，可以利用定理2变成求奇数的。
若p是1个正整数满足 说明该数为素数。把这个数的欧拉函数值改变，同时也把能被该素因子整除的数改变。 void phi()
{
for(int i=1; i<N; i++) p[i] = i;
for(int i=2; i<N; i+=2) p[i] >>= 1;
for(int i=3; i<N; i+=2)
{
if(p[i] == i)
{
for(int j=i; j<N; j+=i)
p[j] = p[j] - p[j] / i;
}
}
} （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
