欧拉函数（Euler's totient function），即 $\varphi(n)$ ，表示的是小于等于 $n$ 和 $n$ 互质的数的个数。
特别地，规定 $\varphi(1)=1$ 。
对于欧拉函数，主要有如下性质：
- 若 $p$ 是质数，则 $\varphi(p^n)=p^{n-1}(p-1)$
- 若 $a|x$ ，则 $\varphi(ax)=a\varphi(x)$
- 若 $a,b$ 互质，则 $\varphi(a)\varphi(b)=\varphi(ab)$
我们把正整数质因数分解：
$$
x=p_1^{k_1} p_2^{k_2}\cdots p_n^{k_n}
$$
所有 $p_i^{k_i}$ 两两互质，由欧拉函数的积性性质有：
$$
\varphi(x)=p_1^{k_1-1}(p_1-1)\cdot p_2^{k_2-1}(p_2-1)\cdots p_n^{k_n-1}(p_n-1)
$$
即：
$$
\varphi(x) = x\cdot\frac{p_1-1}{p_1}\cdot\frac{p_2-1}{p_2}\cdots\frac{p_n-1}{p_n}
$$
用这个式子可以证明上面的性质2.
另外我们可以用这个式子在 $O(\sqrt{n})$ 内求出某个数的欧拉函数。
还可以将其与筛法相结合：
埃氏筛：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N=10000010;
int phi[N],n,sum;
int main(){
cin>>n;
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);//即上面的式子
}
}
for(int i=1;i<=n;i++) cout<<phi[i]<<' ';
return 0;
}
|
$n=10^7$ 时，耗时约 $0.44s$
欧拉筛：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N=10000010;
int phi[N],n,t;
ll sum[N];
bool vis[N];
vector<int>pri;
int main(){
cin>>n;
phi[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]) pri.push_back(i),phi[i]=i-1;
for(int p:pri){
if(p*i>n) break;
vis[i*p]=1;
if(i%p==0){phi[i*p]=phi[i]*p;break;}//这是性质2
phi[i*p]=phi[i]*phi[p];//积性性质
}
}
for(int i=1;i<=n;i++) cout<<phi[i]<<" ";
return 0;
}
|
$n=10^7$ 时，耗时约 $0.48s$