欧拉函数值求解（费马小定理详解）

科技前沿 • 2025-03-19 21:34 • 阅读 34

大家好，我是讯享网，很高兴认识大家。

费马小定理：在p为素数时，对于任意的整数x来说都有x^p=x(mod p)，即：x^(p-1)=1(mod p)。

欧拉定理：当gcd(x,m)==1时，有x^oula(m) = 1 mod m；其中oula（m）为小于n且与n互质的数的个数，称之为欧拉函数

当然大多数情况下，我们可以使用暴力的方法求解oula（m），但效率太低。

假设
讯享网，其中pi为m的质因数，ei为m对应pi下的指数，那么m的欧拉函数的定义如下

在m是素数时，根据定义oula(m)=m-1，因此欧拉定理也可以看作是费马小定理的推广。

我们可以利用埃氏筛法，每次发现质因子时就把他的倍数的欧拉函数乘上(p-1)/p，这样就可以一次性求出1~n的欧拉函数值的表了。

#include<cstdio> #include<cmath> int a[1000]; void f(int n) { for(int i=0; i<n; ++i) a[i]=i; for(int c=2; c<n; ++c) { if(a[c]==c) { for(int j=c; j<n; j+=c) a[j]=a[j]/c*(c-1); } } } int main() { int n; scanf("%d",&n); f(n); for(int i=0; i<n; ++i) printf("%d ",a[i]); return 0; }

讯享网

单独求oula（m）：

讯享网#include<cstdio> #include<cmath> int oula(int n) { if(n==1) return 1; int ans=n,m=sqrt(n); for(int i=2;i<=m;++i) { if(!(n%i)) { ans=ans/i*(i-1); while(!(n%i)) n/=i; } } if(n) ans=ans/n*(n-1); return ans; } int main() { int n; scanf("%d",&n); printf("%d\n",oula(n)); return 0; }

欧拉函数值求解（费马小定理详解）

相关推荐