欧拉函数求法

欧拉函数求法欧拉函数是计算在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互质。具体的证明和其他介绍就不多说了=.

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号