欧拉函数求法

欧拉函数求法

全栈程序员-用户IM • 2022年8月22日下午12:00 • 未分类

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