【定義】

對正整數(shù) n，歐拉函數(shù)是小于等于 n 的數(shù)中與 n 互質(zhì)的數(shù)的個數(shù)，記作：

例如：，因為 1、3、5、7 均與 8 互質(zhì)。

【性質(zhì)】

1）若 n 為一素數(shù) p，則：

2）若 n 為一素數(shù) p 的冪次?，則：

例如：要求?，由于 16=2*2*2*2，故?

3）若 n 為任意兩個互質(zhì)的數(shù) a、b 的積，則：

例如：要求?，由于 40=5*8，且 5、8 互質(zhì)，所以?

4）設(shè)??為 正整數(shù) n 的素數(shù)冪乘積表達(dá)式，則：

5）若?，則：

6）若?，則：

7）前 n 個數(shù)的歐拉函數(shù)的和為：

【求法】

1.一般方法

求一個數(shù) x 的歐拉函數(shù)

int Euler(int x) {int res=x;for(int i=2;i<(int)sqrt(x*1.0)+1;i++){if(x%i==0){res=res/i*(i-1);while(x%i==0)/// 保證i一定是素數(shù)x/=i;}}if(x>1)res=res/x*(x-1);return res; }

2.遞推求法

打表取 1 到 N 的所有歐拉函數(shù)并存在數(shù)組 phi 中

int phi[N]; void Euler() {for(int i=1;i<=N;i++)phi[i]=i;for(int i=2;i<=N;i+= 2)phi[i]/=2;for(int i=3;i<=N;i+= 2){if(phi[i]==i){for(int j=i;j<=N;j+=i)phi[j]=phi[j]/i*(i-1);}} }

3.歐拉函數(shù)線性篩法

該算法可在線性時間內(nèi)篩素數(shù)的同時求出所有數(shù)的歐拉函數(shù)。

如要求一個數(shù)的歐拉函數(shù)，可以用歐拉函數(shù)性質(zhì)直接求出，但是如果要求前 n 個數(shù)的歐拉函數(shù)，可采用線性時間的方法篩選歐拉函數(shù)值，完成打表。

int phi[N],prime[N]; bool vis[N]; void Euler(int n) { int cnt=0;phi[1]=1;for(int i=2;i<=n;i++){if(!vis[i]) {prime[++cnt]=i;//篩素數(shù)的時先判斷i是否是素數(shù) phi[i]=i-1;//當(dāng)i是素數(shù)時phi[i]=i-1 }for(int j=1;j<=cnt;j++){if(i*prime[j]>n)break;vis[i*prime[j]]=1;//確定i*prime[j]不是素數(shù)if(i%prime[j]==0)//看prime[j]是否是i的約數(shù) { phi[i*prime[j]]=phi[i]*prime[j];break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1);//其prime[j]-1就是phi[prime[j]]，利用了歐拉函數(shù)的積性 } } }

【例題】?

Relatives（POJ-2407）(一般求法)：點擊這里

Farey Sequence（POJ-2478）(遞推求法)：點擊這里

Visible Lattice Points（POJ-3090）(線性篩法)：點擊這里

小a與黃金街道（2019牛客寒假算法基礎(chǔ)集訓(xùn)營 Day1-D）(一般求法+公式推導(dǎo))：點擊這里

總結(jié)

以上是生活随笔為你收集整理的数论 —— 欧拉函数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。