歐拉函式
- 什么是歐拉函式
- 怎么計算歐拉函式
- 歐拉函式三種常用模板
- 素因數分解求歐拉函式
- 歐拉函式值打表
- 歐拉篩型歐拉函式
什么是歐拉函式
歐拉函式是小于x的整數中與x互質的數的個數，一般用φ(x)表示，特殊的，φ(1)=1，
例如，φ(12)=4 {1,5,7,11}
怎么計算歐拉函式
φ(x)=X*(1- 1 p 1 \frac{1}{p1} p11?) * (1- 1 p 2 \frac{1}{p2} p21?) * … * (1- 1 p i \frac{1}{pi} pi1?)
其中p1,p2,p3…pi為x的所有質因數（指能整除給定正整數的質數），x是正整數，
比如x=12，12以內有
1
2
\frac{1}{2}
21?的數是2的倍數，還剩下(1,3,5,7,9,11)6個數，這六個數里面又有
1
3
\frac{1}{3}
31?的數是3的倍數還剩下(1,5,7,11)4個數，即4個數與12互質，所以φ(12)=4，
歐拉函式三種常用模板
素因數分解求歐拉函式
int phi(int n) {
int ans = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
ans -= ans / i;//遇到質因數,即X*1/pi
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1)//若n不為1，則還剩下一位質因子
ans -= ans / n;
return ans;
}
歐拉函式值打表
int phi[1000010];
void euler(int n) {
for (int i=1; i<=n; i++) phi[i]=i;//初始化
for (int i=2; i<=n; i++) {
if (phi[i]==i) { //這代表i是質數
for (int j=i; j<=n; j+=i) {
phi[j]=phi[j]/i*(i-1);//此時將素數i的所有倍數全部運用一下
//歐拉公式中的n*(pi-1)/pi,在這里即phi[j] = phi[j] / i * (i - 1)
}
}
}
}
歐拉篩型歐拉函式
#define MAXN 10000000
int phi[MAXN];//即求出的歐拉函式
int flag[MAXN];
int prime[MAXN];//素數表
void euler(int n) {
phi[1]=1;//1要特判
int num=0;//記錄質數總數
for (int i=2; i<=n; i++) {
if (flag[i]==0) { //這代表i是質數
prime[++num]=i;//記錄質數
phi[i]=i-1;//質數的歐拉函式為本身減1
}
for (int j=1; j<=num&&prime[j]*i<=n; j++) { //經典的歐拉篩寫法
flag[i*prime[j]]=1;//先把這個合數標記掉，每個數只由最小質因子篩一次
if (i%prime[j]==0) {
phi[i*prime[j]]=phi[i]*prime[j];//若prime[j]是i的質因子
//則根據計算公式，i已經包括i*prime[j]的所有質因子
break;//經典歐拉篩的核心陳述句，這樣能保證每個數只會被自己最小的因子篩掉一次
}
else
phi[i*prime[j]]=phi[i]*phi[prime[j]]; //利用了歐拉函式是個積性函式的性質
//φ(m*n)=φ(m)*φ(n)
}
}
}
第一次寫博客，分享下自己的初學知識，歡迎大家指出我的錯誤和對博客內容進行補充，謝謝，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278175.html
標籤：其他