大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
欧拉函数是计算在1-n中n的质因数的个数;
φ(x)=x*(p1-1)/p1*(p2-1)/p2*(p3-1)/p3…*(pn-1)/pn
其中p1,p2,p3…是x的质因数;
若x是质数: φ(x)=x-1
若x是质数p的k次幂(即x=p^k):φ(x)=p^k-p^(k-1)=(p-1)p^(k-1)
积性:
φ(n*m)=φ(n)*φ(m)
其中m、n互质。
具体的证明和其他介绍就不多说了=.=
下面开始介绍算法。
暴力求一个欧拉值
嗯,没错很暴力。
用公式:φ(x)=x*(p1-1)/p1*(p2-1)/p2*(p3-1)/p3…*(pn-1)/pn
暴力枚举质因数,不具体说了,看代码喽:
int euler(int x){
int res=x;
for(int i=2;i*i<=x;++i){
if(x%i==0){
res=res/i*(i-1);
while(x%i==0) x/=i;
}
}
if(x>1) res=res/x*(x-1);
return res;
}
打欧拉函数表:
类似于筛法~~~~
所以可以先学习一下筛法=.=
方法一:
类似于埃氏筛?
初始化phi[i]=i;
循环范围内的所有数x;
如果x是质数,将x的倍数乘1-1/x;
原理:φ(x)=x*(p1-1)/p1*(p2-1)/p2*(p3-1)/p3…*(pn-1)/pn(还是它~~~)
void euler()
{
for(int i=1;i<=n;i++)phi[i]=i;
for(int i=2;i<=n;i++)
if(phi[i]==i)
for(int j=i;j<=n;j+=i)
phi[j]=phi[j]/i*(i-1);//防爆先除后乘;
}
方法二:
类似于线性筛?
遍历1-n所有数x;
如果x是质数(m[x]为处理)那么更新phi[x],p[++tot],m[x]值;
对于每一个i用它去乘质数表第j项=k,更新m[k];
原理同线性筛:每一个合数只会被他的最小质因数筛去;
如果m[i]==p[j],更新phi[k]=phi[i]*p[j]break(保证不重复筛某个数);
正确性证明:
phi[i]=i*(p1-1)/p1*(p2-1)/p2*…*(pn-1)/pn
phi[k]=k*(p1-1)/p1*(p2-1)/p2*…*(pn-1)/pn=phi[i]*p[j](k=p[j]*i)
p[j]==m[i]所以p[j]==p1,p[j]-1/p[j]已经包含在phi[i]里;
原理:
1、φ(x)=x*(p1-1)/p1*(p2-1)/p2*(p3-1)/p3…*(pn-1)/pn;
2、若x是质数: φ(x)=x-1。
上代码~:
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 100000000
using namespace std;
int n,tot,p[maxn],m[maxn],phi[maxn];//p-->质数,m-->i的最小质因数,phi-->欧拉值
void euler()
{
phi[1]=1;
tot=0;
int k;
for(int i=2;i<=n;++i)
{
if(!m[i])//i是质数
{
p[tot++]=m[i]=i;//i加入质数表,更新i的最小质因数为i
phi[i]=i-1;//i的欧拉函数值
}
for(int j=0;j<tot&&(k=p[j]*i)<=n;j++)
{
m[k]=p[j];//线性筛的性质,每个合数会被他的最小质因数找到
if(m[i]==p[j])//i的最小质因数为质数表第j项
{
phi[k]=phi[i]*p[j];//phi[i]=i*(p1-1)/p1*(p2-1)/p2*...*(pn-1)/pn而p[j]==m[i]所以p[j]==p1,p[j]-1/p[j]已经包含在phi[i]里;phi[k]=k*(p1-1)/p1*(p2-1)/p2*...*(pn-1)/pn=phi[i]*p[j](k=p[j]*i)
break;//防止重复计算,每个i只由m[i]更新
}
else phi[k]=phi[i]*(p[j]-1);
}
}
}
int main()
{
n=100000000;
euler();
// for(int i=1;i<=n;i++)
// printf("%d %d \n",i,phi[i]);
}
实测:线性筛还是会比埃氏筛快一xu点duo;
跑100000000的欧拉表,线性筛比埃氏筛快0.8-1s~
感谢spli大神教我~ –> 膜一膜spli大神
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/172057.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...