欧拉函数:对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4,因为1,3,5,7均和8互质。

Euler函数表达通式:euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中p1,p2……pn为x的所有素因数,x是不为0的整数。euler(1)=1(唯一和1互质的数就是1本身)。
欧拉公式的延伸:一个数的所有质因子之和是euler(n)*n/2。
欧拉定理:对于互质的正整数a和n,有aφ(n) ≡ 1 mod n。
欧拉函数是积性函数——若m,n互质,φ(mn)=φ(m)φ(n)。
若n是质数p的k次幂,φ(n)=pk-p(k-1)=(p-1)p^(k-1),因为除了p的倍数外,其他数都跟n互质。
特殊性质:当n为奇数时,φ(2n)=φ(n)
欧拉函数还有这样的性质:
设a为N的质因数,若(N % a == 0 && (N / a) % a == 0) 则有E(N)=E(N / a) * a;若(N % a == 0
&& (N / a) % a != 0) 则有:E(N) = E(N / a) * (a - 1)。
那么如何变成实现欧拉函数呢?下面通过两种不同的方法来实现。第一种方法是直接根据定义来实现,同时第一种方法也是第二种筛法的基础,当好好理解。
可以得到关于欧拉函数的递推关系:
假设素数p能整除n,那么
如果p还能整除n / p, PHI(n) = PHI(n / p) * p;
如果p不能整除n / p, PHI(n) = PHI(n / p) * (p - 1);

由对于一个正整数N的素数幂分解N=P1q1*P2q2…Pn^qn.
φ(N)=N(1-1/P1)(1-1/P2)…*(1-1/Pn).*
可以写出以下代码:
直观代码: int euler(int n){ //返回euler(n) int res=n,a=n; for(int i=2;i*i<=a;i++){
// i * i <=a ,因为在分解的时候 a也变小,所以范围也跟着变小 while(a%i==0){ //因为 1-1/p = (p-1)/p . res=
res/i*(i-1);//先进行除法是为了防止中间数据的溢出 a/=i; } } if(a>1) res=res/a*(a-1); return res;
}
但是当求一个区间内的时候上面的方法就不行了,那么我们可以类比以下求素数的优化方法,可不可以用筛法呢?答案是可以!

比如求10以内所有数的φ值: 设一数组phi[11],赋初值phi[1]=1,phi[2]=2...phi[10]=10;
然后从2开始循环,把2的倍数的φ值*(1-1/2),则phi[2]=2*1/2=1,phi[4]=4*1/2=2,phi[6]=6*1/2=3....;
再是3,3的倍数的φ值*(1-1/3),则phi[3]=3*2/3=2,phi[6]=3*2/3=2,phi[9]=.....;
再5,再7...因为对每个素数都进行如此操作,因此任何一个n都得到了φ(n)=n*(1-1/p1)(1-1/p2)....(1-1/pk)的运算

代码:
筛法求欧拉函数: //筛选法打欧拉函数表 #define Max 1000001 int euler[Max]; void Init(){ euler[1]=
1; for(int i=2;i<Max;i++) euler[i]=i; for(int i=2;i<Max;i++) if(euler[i]==i)
//所以这里i这能是素数 for(int j=i;j<Max;j+=i) //j = j+i,那么是i的倍数的数都会改变 euler[j]=euler[j]/
i*(i-1);//先进行除法是为了防止中间数据的溢出 }
也可以在筛法中进行初始化
代码:void Euler() { for (int i = 2; i < N; i++) { if (!phi[i]) for (int j = i; j
< N; j += i) { if (!phi[j])phi[j] = j; phi[j] = phi[j] / i * (i - 1); } } }

技术
今日推荐
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信