前言
欧拉函数听起来很高大上，但其实非常简单，也是NOIP里的一个基础知识，希望大家看完我的博客能有所理解。
数论是数学的一个分支，它只讨论正整数的性质，所以以下都是针对正整数进行研究的。
什么是欧拉函数
欧拉函数是小于x的整数中与x互质的数的个数，一般用φ(x)表示。特殊的，φ(1)=1。
如何计算欧拉函数
通式： φ(x)=x
∏
i
=
1
n
(
1
−
1
p
i
)
\prod_{i=1}^n{(1-\frac{1}{p_i})}
∏
i
=
1
n
(
1
−
p
i
1
)
φ(1)=1
其中
p
1
p_1
p
1
,
p
2
p_2
p
2
……
p
n
p_n
p
n
为x的所有质因数，x是正整数。
那么，怎么理解这个公式呢？对于x的一个质因数
p
i
p_i
p
i
，因为x以内
p
i
p_i
p
i
的倍数是均匀分布的，所以x以内有
1
p
i
\frac {1}{p_i}
p
i
1
的数是
p
i
p_i
p
i
的倍数，那么有1-
1
p
i
\frac {1}{p_i}
p
i
1
的数不是
p
i
p_i
p
i
的倍数。再对于
p
j
p_j
p
j
，同理，有1-
1
p
j
\frac {1}{p_j}
p
j
1
的数不是
p
j
p_j
p
j
的倍数，所以有
(
1
−
1
p
i
)
∗
(
1
−
1
p
j
)
(1-\frac {1}{p_i})*(1-\frac {1}{p_j})
(
1
−
p
i
1
)
∗
(
1
−
p
j
1
)
的数既不是
p
i
p_i
p
i
的倍数，又不是
p
j
p_j
p
j
的倍数。最后就有
∏
i
=
1
n
(
1
−
1
p
i
)
\prod_{i=1}^n{(1-\frac{1}{p_i})}
∏
i
=
1
n
(
1
−
p
i
1
)
的数与x互质，个数自然就是x
∏
i
=
1
n
(
1
−
1
p
i
)
\prod_{i=1}^n{(1-\frac{1}{p_i})}
∏
i
=
1
n
(
1
−
p
i
1
)
。
还不理解？没关系，举个例子。比如x=12，12以内有
1
2
\frac {1}{2}
2
1
的数是2的倍数，那么有1-
1
2
\frac {1}{2}
2
1
的数不是2的倍数（1,3,5,7,9,11），这6个数里又有
1
3
\frac {1}{3}
3
1
的数是3的倍数，只剩下(1-
1
2
\frac {1}{2}
2
1
)* (1-
1
3
\frac {1}{3}
3
1
)的数既不是2的倍数，也不是3的倍数（1,5,7,11）。这样剩下的 12*(1-
1
2
\frac {1}{2}
2
1
)*(1-
1
3
\frac {1}{3}
3
1
)，即4个数与12互质，所以φ(12)=4。
积性函数
先介绍一下什么是积性函数，后面将会用到。若当m与n互质时，
f
(
m
∗
n
)
=
f
(
m
)
∗
f
(
n
)
f(m*n)=f(m)*f(n)
f
(
m
∗
n
)
=
f
(
m
)
∗
f
(
n
)
，那么f是积性函数。若对任意正整数，都有f(m*n)=f(m)*f(n)成立，则f是完全积性函数。
欧拉函数的几个性质
1.对于质数p，
φ
(
p
)
=
p
−
1
φ(p)=p-1
φ
(
p
)
=
p
−
1
。
2.若p为质数，
n
=
p
k
n=p^k
n
=
p
k
，则
φ
(
n
)
φ(n)
φ
(
n
)
=
p
k
p^k
p
k
–
p
k
−
1
p^{k-1}
p
k
−
1
。
3.欧拉函数是积性函数，但不是完全积性函数。若m,n互质，则
φ
(
m
∗
n
)
=
φ
(
m
)
∗
φ
(
n
)
φ(m*n)=φ(m)*φ(n)
φ
(
m
∗
n
)
=
φ
(
m
)
∗
φ
(
n
)
。特殊的，当m=2，n为奇数时，φ(2*n)=φ(n)。
4.当n>2时，φ(n)是偶数。
5.小于n的数中，与n互质的数的总和为：φ(n) * n / 2 (n>1)。
6.
n
=
∑
d
∣
n
φ
(
d
)
n=\sum_{d|n}{φ(d)}
n
=
∑
d
∣
n
φ
(
d
)
，即n的因数（包括1和它自己）的欧拉函数之和等于n。
欧拉函数性质的粗略证明
1.因为p是质数，所以1到n-1都与n互质。
2.n只有一个质因数p，根据公式φ(x)=x
∏
i
=
1
n
(
1
−
1
p
i
)
=
x
∗
(
1
−
1
p
)
=
p
k
∗
(
1
−
1
p
)
=
p
k
−
p
k
−
1
\prod_{i=1}^n{(1-\frac{1}{p_i})} =x*(1-\frac{1}{p})=p^k*(1-\frac{1}{p})=p^k-p^{k-1}
∏
i
=
1
n
(
1
−
p
i
1
)
=
x
∗
(
1
−
p
1
)
=
p
k
∗
(
1
−
p
1
)
=
p
k
−
p
k
−
1
。
3.因为m与n互质，所以它们没有公共的质因数。设m有
a
m
a_m
a
m
个质因数，n有
a
n
a_n
a
n
个质因数。
φ
(
m
)
∗
φ
(
n
)
=
m
∗
n
∗
∏
i
=
1
a
m
(
1
−
1
p
i
)
∗
∏
i
=
1
a
n
(
1
−
1
p
i
)
=
m
∗
n
∗
∏
i
=
1
a
m
+
a
n
(
1
−
1
p
i
)
=
φ
(
m
∗
n
)
φ(m)* φ(n)=m*n * \prod_{i=1}^{a_m}{(1-\frac{1}{p_i})}*\prod_{i=1}^{a_n}{(1-\frac{1}{p_i})}=m*n * \prod_{i=1}^{a_m+a_n}{(1-\frac{1}{p_i})}=φ(m*n)
φ
(
m
)
∗
φ
(
n
)
=
m
∗
n
∗
∏
i
=
1
a
m
(
1
−
p
i
1
)
∗
∏
i
=
1
a
n
(
1
−
p
i
1
)
=
m
∗
n
∗
∏
i
=
1
a
m
+
a
n
(
1
−
p
i
1
)
=
φ
(
m
∗
n
)
。
4.前几个都可以利用公式证明，这个却不行。首先有一个基本事实（我不想证明），若gcd(n,m)=1，则gcd(n,n-m)=1（设n>m)。当m=n-m时，
n
=
2
∗
m
n=2*m
n
=
2
∗
m
，那么n>2时gcd(n,m)<>2，与前提相悖，故m<>n-m。换句话说，n>2时，与n互质的数是成对出现的，所以φ(n)必为偶数。
5.证明这个也要用到上面所说的基本事实。与n互质的数一个是m，那么还存在另一个数n-m也与n互质。所以与n互质的数的平均数是n/2，而个数又是φ(n)，可以得到这些数的和就是φ(n)*n/2。
6.证明1（理性的证明）：
这个证明起来有点麻烦。设F(n)=
∑
d
∣
n
φ
(
d
)
\sum_{d|n}{φ(d)}
∑
d
∣
n
φ
(
d
)
。首先证明F(n)是个积性函数：设m，n互质，则要证
F
(
m
∗
n
)
=
F
(
m
)
∗
F
(
n
)
F(m*n)=F(m)*F(n)
F
(
m
∗
n
)
=
F
(
m
)
∗
F
(
n
)
。
F
(
m
)
∗
F
(
n
)
=
∑
i
∣
m
φ
(
i
)
∗
∑
j
∣
n
φ
(
j
)
=
φ
(
i
1
)
∗
φ
(
j
1
)
+
φ
(
i
1
)
∗
φ
(
j
2
)
+
.
.
.
+
φ
(
i
2
)
∗
φ
(
j
1
)
+
φ
(
i
2
)
∗
φ
(
j
2
)
+
.
.
.
+
φ
(
i
k
m
)
∗
φ
(
j
k
n
)
F(m)*F(n)=\sum_{i|m}{φ(i)}*\sum_{j|n}{φ(j)}=φ(i_1)*φ(j_1)+φ(i_1)*φ(j_2)+…+φ(i_2)*φ(j_1)+φ(i_2)*φ(j_2)+…+φ(i_{km})*φ(j_{kn})
F
(
m
)
∗
F
(
n
)
=
∑
i
∣
m
φ
(
i
)
∗
∑
j
∣
n
φ
(
j
)
=
φ
(
i
1
)
∗
φ
(
j
1
)
+
φ
(
i
1
)
∗
φ
(
j
2
)
+
.
.
.
+
φ
(
i
2
)
∗
φ
(
j
1
)
+
φ
(
i
2
)
∗
φ
(
j
2
)
+
.
.
.
+
φ
(
i
k
m
)
∗
φ
(
j
k
n
)
这里假设
i
1
,
i
2
,
.
.
.
i
k
m
i_1,i_2,…i_{km}
i
1
,
i
2
,
.
.
.
i
k
m
为m的所有因数，
j
1
,
j
2
,
.
.
.
j
k
n
j_1,j_2,…j_{kn}
j
1
,
j
2
,
.
.
.
j
k
n
为n的所有因数之和，因为m与n互质，所以它们的因数也必然全都两两互质，而欧拉函数又是个积性函数，即
φ
(
i
k
∗
j
k
)
=
φ
(
i
k
)
∗
φ
(
j
k
)
φ(i_k*j_k)=φ(i_k)*φ(j_k)
φ
(
i
k
∗
j
k
)
=
φ
(
i
k
)
∗
φ
(
j
k
)
，那么上式又可以等价于
φ
(
i
1
∗
j
1
)
+
φ
(
i
1
∗
j
2
)
+
.
.
.
+
φ
(
i
2
∗
j
1
)
+
φ
(
i
2
∗
j
2
)
+
.
.
.
+
φ
(
i
k
m
∗
j
k
n
)
。
φ(i_1*j_1)+φ(i_1*j_2)+…+φ(i_2*j_1)+φ(i_2*j_2)+…+φ(i_{km}*j_{kn})。
φ
(
i
1
∗
j
1
)
+
φ
(
i
1
∗
j
2
)
+
.
.
.
+
φ
(
i
2
∗
j
1
)
+
φ
(
i
2
∗
j
2
)
+
.
.
.
+
φ
(
i
k
m
∗
j
k
n
)
。
可以发现，
i
1
∗
j
1
,
i
1
∗
j
2
,
.
.
.
,
i
2
∗
j
1
,
i
2
∗
j
2
,
.
.
.
,
i
k
m
∗
j
k
n
i_1*j_1,i_1*j_2,…,i_2*j_1,i_2*j_2,…,i_{km}*j_{kn}
i
1
∗
j
1
,
i
1
∗
j
2
,
.
.
.
,
i
2
∗
j
1
,
i
2
∗
j
2
,
.
.
.
,
i
k
m
∗
j
k
n
这些数构成了
m
∗
n
m*n
m
∗
n
的所有因数。那么这些数的欧拉函数之和就等于
F
(
m
∗
n
)
F(m*n)
F
(
m
∗
n
)
，所以
F
(
m
∗
n
)
=
F
(
m
)
∗
F
(
n
)
F(m*n)=F(m)*F(n)
F
(
m
∗
n
)
=
F
(
m
)
∗
F
(
n
)
，证得F是一个积性函数。根据这个性质，F可以一直分解到n为质数的幂的情况。那么讨论当p为质数时，F(p^k)怎么计算。因为
p
k
p^k
p
k
的因数只有
1
,
p
,
p
2
,
p
3
,
.
.
.
,
p
k
1,p,p^2,p^3,…,p^k
1
,
p
,
p
2
,
p
3
,
.
.
.
,
p
k
，根据F的定义，直接展开来计算就行了。（根据欧拉函数的性质2，φ(
p
k
p^k
p
k
)=
p
k
−
p
(
k
−
1
)
p^k-p^(k-1)
p
k
−
p
(
k
−
1
)
）
F
(
p
k
)
=
φ
(
1
)
+
φ
(
p
)
+
φ
(
p
2
)
+
.
.
.
+
φ
(
p
k
)
=
1
+
(
p
−
1
)
+
(
p
2
−
p
)
+
.
.
.
+
(
p
k
−
p
(
k
−
1
)
)
=
p
k
。
F(p^k)=φ(1)+φ(p)+φ(p^2)+…+φ(p^k)=1+(p-1)+(p^2-p)+…+(p^k-p^(k-1))=p^k。
F
(
p
k
)
=
φ
(
1
)
+
φ
(
p
)
+
φ
(
p
2
)
+
.
.
.
+
φ
(
p
k
)
=
1
+
(
p
−
1
)
+
(
p
2
−
p
)
+
.
.
.
+
(
p
k
−
p
(
k
−
1
)
)
=
p
k
。
既然对于质数的幂，F(n)=n成立，而F又是个积性函数，这个结论就可以扩展到任意正整数了。至此，命题得证。
证明2（感性的证明）：
以12为例。12的因子有1,2,3,4,6,12。把与这些数互质的数列出来：
1:1
2:1
3:1 2
4:1 3
6:1 5
12 1 5 7 11
不妨把这些数作为分母，把与这些数互质的数作为分子，写成分数形式：
1/1
1/2
1/3 2/3
1/4 3/4
1/6 5/6
1/12 5/12 7/12 11/12
显然，每一行的数的个数就是该行的分母的欧拉函数值。倘若把这些数都改成以12为分母的数：
12/12
6/12
4/12 8/12
3/12 9/12
2/12 10/12
1/12 5/12 7/12 11/12
可以发现，这些数是以12为分母，1~12为分子的所有数，所以个数为12个。所以与12互质的数的欧拉函数值之和就是12。这样，命题大概就被证明了吧。
求欧拉函数
埃拉托斯特尼筛求欧拉函数
观察欧拉函数的公式，φ(x)=x
∏
i
=
1
n
(
1
−
1
p
i
)
\prod_{i=1}^n{(1-\frac{1}{p_i})}
∏
i
=
1
n
(
1
−
p
i
1
)
= x
∏
i
=
1
n
p
i
−
1
p
i
\prod_{i=1}^n{\frac{p_i-1}{p_i}}
∏
i
=
1
n
p
i
p
i
−
1
。我们用phi[x]表示φ(x)。可以一开始把phi[x]赋值为x，然后每次找到它的质因数就
p
h
i
[
x
]
=
p
h
i
[
x
]
/
p
i
∗
(
p
i
−
1
)
phi[x]=phi[x]/p_i*(p_i-1)
p
h
i
[
x
]
=
p
h
i
[
x
]
/
p
i
∗
(
p
i
−
1
)
（先除再乘，避免溢出）。当然，若只要求一个数的欧拉函数，可以从1到sqrt(n)扫一遍，若gcd(i,n)=1就更新
p
h
i
[
n
]
phi[n]
p
h
i
[
n
]
。复杂度为O(logn)（代码就不给了）。那要求1~n所有数的欧拉函数呢？可以用埃拉托斯特尼筛的思想，每次找到一个质数，就把它的倍数更新掉。这个复杂度虽然不是O(n)，但还是挺快的（据说是O(n*ln ln n)，关于证明，可以点
这里
，虽然我看不懂）。
代码如下：
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的倍数更新掉
}
}
}
}
欧拉筛求欧拉函数
前提是要懂欧拉筛。每个数被最小的因子筛掉的同时，再进行判断。i表示当前做到的这个数，prime[j]表示当前做到的质数，那要被筛掉的合数就是i*prime[j]。若prime[j]在这个合数里只出现一次（i%prime[j]!=0），也就是i和prime[j]互质时，则根据欧拉函数的积性函数的性质，phi[i * prime[j]]=phi[i] * phi[prime[j]]。若prime[j]在这个合数里出现了不止一次（i%prime[j]=0），也就是这个合数的所有质因子都在i里出现过，那么根据公式，φ(i * prime[j])=prime[j] * i *
∏
k
=
1
n
(
1
−
1
p
k
)
\prod_{k=1}^n{(1-\frac{1}{p_k})}
∏
k
=
1
n
(
1
−
p
k
1
)
=φ(i) *prime[j]。复杂度为O(n)。
还是看代码吧：
void euler(int n)
{
phi[1]=1;//1要特判
for (int i=2;i<=n;i++)
{
if (flag[i]==0)//这代表i是质数
{
prime[++num]=i;
phi[i]=i-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]];//利用了欧拉函数是个积性函数的性质
}
}
}
总结
有关欧拉函数的性质，只需做个了解，而求欧拉函数的代码，却是一定要会写的。这只是走进数论世界的第一步。