【学习笔记】欧拉函数基础

欧拉函数的定义

\varphi(n)

为

\{1,2,\dots,n\}

中与

n

互质的数的个数，这称为欧拉函数。

欧拉函数的基本性质

如果 $n$ 为质数，那么 $\varphi(n)$ 的值为 $n-1$ 。
若 $n$ 与 $m$ 互质，那么 $\varphi(nm)=\varphi(n)\times\varphi(m)$ ，这是因为欧拉函数是积性函数。
若 $k$ 为质数，那么 $\phi(p^k) \times p^k (p-1)$ 。

欧拉函数的计算公式

根据唯一分解定理

n = \prod_{i = 1}^{s} p_{i}^{\alpha_{i}} = p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{s}^{\alpha_{s}}

\varphi(n)

=\prod_{i = 1}^{s}\varphi(p_{i}^{\alpha_{i}})

=\prod_{i = 1}^{s} p_{i}^{\alpha_{i}-1}(p_{i} - 1)

=\prod_{i = 1}^{s} p_{i}^{\alpha_{i}} \times \prod_{i = 1}^{s}(1 - \frac{1}{p_{i}})

n \times \frac{p_{1}-1}{p_{1}} \times \frac{p_{2}-1}{p_{2}} \times \cdots \times \frac{p_{s}-1}{p_{s}}

注意：欧拉函数只和

n

的质因子有关系。

例子

\varphi(30) = 30 \times \frac{5-1}{5} \times \frac{3-1}{3} \times \frac{2-1}{2} = 8

实际上

1

到

30

中，与

30

互质的数有

\{1, 7, 11, 13, 17, 19, 23, 29\}

共

8

个。

φ函数的实现

不优化版

我们已经知道了欧拉函数的公式为

$\varphi(n)=n \times \frac{p_{1}-1}{p_{1}} \times \frac{p_{2}-1}{p_{2}} \times \cdots \times \frac{p_{s}-1}{p_{s}}$

而且欧拉函数只和

n

的质因子有关系，那么我们可以一个一个枚举

n

的质因子，再乘上

\frac{p_{i}-1}{p_{i}}

就可以得到了；注意：

n

每找到一个质因子

p_{i}

时，一定要把

n

的

p_{i}

除尽为止。

Code

CPP

int phi(int n){
    int res=n;//res初始化为n 
    for(int i=2;i*i<=n;i++){//枚举可能的因子 
        if(n%i==0){//如果i是因子(这里一定是质数，不然在前面已经被筛过了) 
            res=res/i*(i-1);//应用欧拉函数的公式 
            while(n%i==0)//除尽所有i的因子 
				n/=i;
        }
    }
    if(n>1)//处理剩余的质因子 
		res=res/n*(n-1);
    return res;//返回res 
}

线性优化版

我们可以优化——用线性筛法进行优化，我们知道线性筛法的方法只筛到一个最小的质因数就标记，所以我们可以通过线性筛来优化欧拉函数。

具体的

若

i

为质数，那么

phi_i=i-1

，并记录质数。
在线性筛中，每个和数

m

都是被最小的质因子筛掉的。
设

p_{j}

是

m

的最小质因子，则

m

是通过

m=p_{j}\times i

筛掉的。

若 $i$ 能被 $p_{j}$ 整除，则 $i$ 包含了 $m$ 的所有质因子。
$\varphi(m)=p_{j}\times\varphi(i)$ 。
若 $i$ 不能被 $p{j}$ 整除，则 $i$ 和 $p_{j}$ 是互质的。
$\varphi(m)=p_{j}\times\varphi(i)$ 。

Code

CPP

const int N=1000005;
int p[N],vis[N],cnt,phi[N];
void g_phi(int n){//欧拉筛法求1到n的phi值 
	phi[1]=1;//1的欧拉函数值为1 
	for(int i=2;i<=n;i++){
		if(!vis[i]){//i为质数 
			p[++cnt]=i;//记录质数 
			phi[i]=i-1;//指数的phi值为i-1 
		}
		for(int j=0;i*p[i]<=n;j++){//用i和所有质数p[j]的乘积筛 
			int m=i*p[j];
			vis[m]=1;//m为非质数 
			if(i%p[j]==0){//如果i为p[j]的倍数 
				phi[m]=p[j]*phi[i];//根据欧拉函数的积性性质计算 
				break;//跳出内层循环 
			}
			else
				phi[m]=(p[j]-1)*phi[i];
		}
	}
}

例题

互质

这题只要认真看上面我介绍的都可以做出来，是一道水题~~主要是真的不知道写啥了~~。

思路
因为我们已经知道它要求的数是在

[1,2023^{2023}]

中有多少个数和

2023

互质，根据欧拉函数的计算公式。
第一步我们可以先分解质因数：

2023=7\times17^2

第二步我们可以通过欧拉函数的性质转化成：

= 2023^{2022} \times 2023 \times \frac{6}{7} \times \frac{16}{17} \\ = 1632 \times 2023^{2022}

我们再用快速幂结合欧拉函数就好啦！

ACのCode

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Mod=1e9+7;
int qpow(int a,int b){//快速幂
    int ans=1;
    a%=Mod; //初始值取模
    while(b>0){
        if(b%2==1) ans=(ans*a)%Mod;
        a=(a*a)%Mod;
        b/=2;
    }
    return ans;
}
signed main(){
    int k1=2023*(7-1)/7*(17-1)/17; //phi[2023]
    int k2=qpow(2023,2022); //计算2023的2022次方模Mod
    cout<<(k1*k2)%Mod;
    return 0;
}

互质数的个数

思路

这题是一道基础的欧拉函数的题目，通过观察~~直接看~~题目，我们就可以想到上文的基本性质三。

若 $k$ 为质数，那么 $\varphi(p^k)=p^{k - 1}\varphi(p - 1)$ 。

然后我们看到数据范围是：

1 < a \leq 10^9,1 \leq b \leq 10^{18}

，这我们想到了快速幂，然后再搭配欧拉函数

\varphi(a-1)

我们就可以做出这题了。

时间复杂度分析：

如果不用线性优化

\varphi(a-1)

会不会超时呢？我们知道欧拉函数（不优化）的复杂度是

\operatorname{O}(\sqrt{a}\log(a))

，通过计算，最大的复杂度也只是来到了

284605

左右，所以不会超时。

ACのCode

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int mod=998244353;
int qpow(int p,int k){//快速幂
    int res=1;
    while(k){
        if(k&1)res=(res*p)%mod;
        p=(p*p)%mod;
        k>>=1;
    }
    return res;
}
int phi(int n){//phi函数
    int res=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            res=res/i*(i-1);
            while(n%i==0)
				n/=i;
        }
    }
    if(n>1)res=res/n*(n-1);
    return res;
}
signed main(){
    int a,b;
    cin>>a>>b;
    int ans=(qpow(a,b-1)*(phi(a)%mod))%mod;
    cout<<ans;
    return 0;
}

参考文献：互质题解&OI-wiki&B站视频。

【学习笔记】欧拉函数基础

文章操作

欧拉函数的定义

欧拉函数的基本性质

欧拉函数的计算公式

φ函数的实现

不优化版

线性优化版

具体的

例题

互质

互质数的个数

思路

时间复杂度分析：

相关推荐

评论

【学习笔记】欧拉函数基础