欧拉函数
在数论，对正整数n，欧拉函数是小于等于n的正整数中与n互质的数的数目。读作 phi 。\(\LaTeX\) 大写：\phi \(\phi\) ，小写：\varphi \(\varphi\)
部分选自百度百科
欧拉函数的性质
以下所有 \(p\) 表示 质数
性质1
\[\varphi(p)=p-1 \]性质1的证明
根据质数的定义，比 p 小的数都是与 p 互质的，所以1到n-1都与n互质。这一点很容易得出。
性质2
欧拉函数是积性函数，但不是完全积性函数。
什么意思呢？若 \(\gcd(a,b)=1\) 则有 \(\varphi(a\times b)=\varphi(a)\times\varphi(b)\) 。
性质2的证明之理性证明
\[\begin{aligned} \varphi(m)* \varphi(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})} \\ &= \varphi(m*n) \end{aligned} \]性质2的证明之感性证明
因为 ab互质，所以与a互质的数乘上与b互质的数也会与ab互质
性质3
\[\varphi(p^k)=p^k-p^{k-1} \]性质3的证明
因为 \(p\) 是质数，与 \(p^k\) 互质的有 \(p,2p,3p...p\times p^{k-2},p\times p^{k-1}\) ，共 \(p^{k-1}\) 个，故用全部个数减去互质个数得 \(\varphi(p^k)=p^k-p^{k-1}\) 。
性质4
\[\varphi(n) = n \times \prod_{i = 1}^s{(1-\frac{1}{p_i})} \]性质4的证明
这里的n没有质不质数的限制，根据 唯一分解定理 ，一个大于1的正整数，分解后一定是这样的形式：
\[n = p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times ... \times p_s^{a_s} = \prod_{i = 1}^s{p_i^{a_i}} \]根据性质2（ \(\varphi(a\times b)=\varphi(a)\times\varphi(b)\) ）得：
\[\varphi(n) = \varphi(p_1^{a_1}) \times ... \times \varphi(p_s^{a_s}) \]再根据性质3（ \(\varphi(p^k)=p^k-p^{k-1}\) ）得：
\[\varphi(n) = (p_1^{a_1}-p_1^{a_1-1}) \times ... \times (p_s^{a_s}-p_s^{a_s-1}) \]整理一下，疯狂化简：
\[\begin{eqnarray} \varphi(n)&=&\prod_{i = 1}^s{p_i^{a_i}-p_i^{a_i-1}} \nonumber \\ ~&=&\prod_{i = 1}^s{p_i^{a_i}(1-\frac{1}{p_i})} \nonumber \\ ~& &\text{根据 唯一分解定理 } n = \prod_{i = 1}^s{p_i^{a_i}} &\text{ 得到} \nonumber \\ ~&=&n \times \prod_{i = 1}^s{(1-\frac{1}{p_i})} \nonumber \end{eqnarray} \]性质5
\[\sum_{i = 1}^n{i[gcd(i,n)=1]}=n\frac{\varphi(n)}{2} \]此处 [] 表示条件，若 [] 内条件为真则为 1，反之为 0 。
性质5的证明
由 \(\gcd(n,i)=1\) 可证出 \(\gcd(n,n-i)=1\)
证明当 \(\gcd(n,i)=1\) 时 \(\gcd(n,n-i)=1\)
设 \(\gcd(n,n-i)=D\neq 1\) ，则有 \(D|n\) 、 \(D|n-i\) 。
所以 \(D|i\) （因为n是D的倍数，n-i是D的倍数，所以i是D的倍数）
根据 \(D|n\) 、 \(D|i\) 得到 \(\gcd(n,i)\geq D\) 。根据条件 \(\gcd(n,i)=1\) 得 \(D=1\) ，与 \(D\neq 1\) 矛盾。故当 \(\gcd(n,i)=1\) 时 \(\gcd(n,n-i)=1\) 。
继续证性质5
因为 \(\gcd(n,i)=1\) 可证出 \(\gcd(n,n-i)=1\) 。
所以与 \(n\) 互质的数的组数是 \(\frac{\varphi(n)}{2}\) （总共 \(\varphi(n)\) 个数，两个数凑成一组），而每组之和又是 \(n\) ，可以得到这些数的和就是 \(n\frac{\varphi(n)}{2}\) 。
如当 \(n=12\) 时符合条件的i有 1 5 7 11 ，1和11可以凑成一组 与 5和7可以凑成一组，总共是两组，故总共是 \(2\times \frac{4}{2} = 4\) 。
性质6
\[n=\sum_{d|n}{\varphi(d)} \]在这里 d|n 表示d是n的因数（包括1和它自己）
性质6的证明
设 \(F(n)=\sum_{d|n}{\varphi(d)}\)
- 如果n=1，\(\varphi(n)=1=n\) ，满足 \(F(n)=n\) 。
- 如果n是质数， \(\varphi(n)=n−1\)，所以 \(\varphi(n)+\varphi(1)=1\) ，满足 \(F(n)=n\) 。
- 如果n是一个质数p的幂，即 \(n=p^k\) ，因为 \(p^k\) 的因数只
1,p,p2,p3,⋯,pk，根据性质3（ \(\varphi(p^k)=p^k-p^{k-1}\) ），代入计算\(F(p^k)=\varphi(1)+\varphi(p)+\varphi(p^2)+...+\varphi(p^k)=1+(p-1)+(p^2-p)+...+(p^k-p^{k-1})=p^k\) ，满足 \(F(n)=n\) 。 - 如果n有多个质因子，即 \(n=p_1^{k_1}p_2^{k_2}...p_n^{k_n}\) 。
首先证明 \(F(n)\) 是个积性函数：设m,n互质，则要证 \(F(m\times n)=F(m)\times F(n)\) 。
\[\begin{aligned} F(m)∗F(n) &= \sum_{i|m}{\varphi(i)}\times\sum_{j|n}{\varphi(j)} \\ &= (\varphi(i_1) + \varphi(i_2) + ... + \varphi(i_{pm})) \times (\varphi(i_1) + \varphi(i_2) + ... + \varphi(i_{qn})) \\ &= \varphi(i_1)\times\varphi(j_1)+\varphi(i_1)\times\varphi(j_2)+...+\varphi(i_1)\times\varphi(j_{qn}) &(\text{这里可以想到乘法分配律})\\ &\quad +\varphi(i_2)\times\varphi(j_1)+\varphi(i_2)\times\varphi(j_2)+...+\varphi(i_2)\times\varphi(j_{qn}) \\ &\quad +...\\ &\quad +\varphi(i_{pm})\times\varphi(j_1)+\varphi(i_{pm})\times\varphi(j_2)+...+\varphi(i_{pm})\times\varphi(j_{qn}) \end{aligned} \]其中 \(i_1,i_2,... ,i_{pm}\) 为m的所有因数， \(j_1,j_2,\cdots,j_{qn}\) 为n的所有因数。
因为m与n互质，所以它们的因数也必然全都两两互质，而欧拉函数又是个积性函数，即 \(\varphi(a\times b)=\varphi(a)\times\varphi(b)\) ，那么上式又可以等价于 \(\varphi(i_1\times j_1)+\varphi(i_1\times j_2)+...+\varphi(i_{pm}\times j_{qn})\) 。可以发现，这些数构成了 \(m\times n\) 的所有因数。那么这些数的欧拉函数之和就等于 \(F(m\times n)\) ，所以 \(F(m\times n)=F(m)\times F(n)\) ，证得F是一个积性函数。
根据 唯一分解定理 ，$ n = p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times ... \times p_s^{a_s} $
所以 \(F(n)=F(p_1^{k_1})\times F(p_2^{k_2})\times ...\times F(p_n^{k_n})=p_1^{k_1}p_2^{k_2}... p_n^{k_n}=n\)
综上， \(F(n)=n\) 对所有的正整数n成立。
故 \(n=\sum_{d|n}{\varphi(d)}\)
性质7
当 \(n>2\) 时， \(\varphi(n)\) 是偶数
性质7的证明
- 当n为质数时，根据性质1可得 \(\varphi(n)=n-1\) ，大于2的质数均为奇数，故当 \(n>2\) 且为质数时 \(\varphi(n)=n-1\) 是偶数。
- 当n为和数且 \(n=2^k\) 时，k一定大于1（如果k=1，则n就是2了）。\(\varphi(2^k)=2^k-2^{k-1}=(2^k-1)\times (2^{k-1})\) ， \(2^{k-1}\) 一定是一个偶数（注意前面的前提——k大于1） ，偶数乘任意整数依旧是偶数，则 \(\varphi(2^k)=(2^k-1)\times (2^{k-1})\) 是偶数。
- 当n为和数且 \(n\neq 2^k\) 时，根据性质4可得 \(\varphi(n) = \prod_{i = 1}^s{p_i^{a_i}-p_i^{a_i-1}} = \prod_{i = 1}^s{(p_i-1)\times p_i^{a_i-1}}\) 。
此时对于每一个 \(p_i\) 不为2的 \((p_i-i)\times p_i^{a_i-1}\) （这一个 \(p_i\) 一定存在，不然n就是2的k次幂，是情况2了）， \(p_i-1\) 一定为偶数（因为p是大于2的质数），故 \((p_i-i)\times p_i^{a_i-1}\) 一定也是偶数。所以 \(\prod_{i = 1}^s{(p_i-1)\times p_i^{a_i-1}}\) 至少存在着一个偶数，偶数乘任意整数还为偶数，故 \(\varphi(n) = \prod_{i = 1}^s{(p_i-1)\times p_i^{a_i-1}}\) 是偶数。
综上 \(\varphi(n)\) 是偶数 对所有大于2的正整数n成立。得证。
欧拉函数计算代码
lazy_phi
根据欧拉算法的定义，我们可以写出这么一个代码：
template<typename T>
T gcd(T a,T b){
if(b==0) return a;
return gcd(b,a%b);
}
template<typename T>
T lazy_phi(T n){ // lazy_phi的名字是我自己起的
T res=0;
for(T i=1;i<=n;i++){
if(gcd(i,n)==1){
res++;
}
}
return res;
}
的确挺 lazy 的。复杂度……反正很大。
但是，我们可以优化一下：
good_phi
我们先假设 \(\varphi(n)=n\) ，每遇到一个n的因数k就将它与它的倍数的个数减去。我们可以求出n以内因数k的出现次数为： \(\lfloor\frac{phi[n]}{k}\rfloor\) ，即更新为 \(phi[n]-=\lfloor\frac{phi[n]}{k} \rfloor\) （即先求出在n范围内k的倍数出现了多少次，再减去所有k的倍数）
template<typename T>
T good_phi(T n){
T res=n;
for(T i=2;i*i<=n;i++){
if(n%i==0){
res-=res/i;
}
while(n%i==0) n/=i; // 刚刚算过了
}
if(n>1) res-=res/n; // 最后的n也是因数
return res;
}
erat_phi
我们既然前面得出了 \(phi[n]-=\lfloor\frac{phi[n]}{k} \rfloor\) ，为何不一次性把所有phi求出来呢？我们在这里使用 埃拉托斯特尼筛 ：
int phi[N+10]; // phi值
template<typename T>
void erat_phi(T n){
for(T i=1;i<=n;i++) phi[i]=i;
for(T i=2;i<=n;i++){
if(phi[i]==i){
for(int j=i;j<=n;j+=i){ // 更新倍数
phi[j]-=phi[j]/i;
}
}
}
}
euler_phi
注意到在欧拉筛中，每一个合数都是被最小的质因子筛掉。我们可以利用这个性质来实现求phi。
case 1 对于每一个质数，都有 \(\varphi(p)=p-1\) 。
case 2 若 a 不是是质数 p 的倍数 ，因为 \(\varphi\) 是积性函数，故有 \(\varphi(a\times p)=\varphi(a)\times \varphi(p)\)
case 3 若 a 是质数 p 的倍数，则有 \(\varphi(a\times p) = \varphi(i) \times p\) 。
证明 \(\varphi(a\times p) = \varphi(a) \times p\)
我们用矩阵的方式想：有一个a列p行的矩阵，由于a是p的倍数，那么我们就只用考虑与a互质的数即可。因为与a互质的数就是与 \(a\times p\) 互质的数，即当 \(k\not\mid a\) 时 ， \(k\times i\not\mid a\times p\) 。
\[\begin{array}{} 1 & 2 & \cdots & a\\ a+1 & a+2 & \cdots & 2a\\ \vdots & \vdots & \ddots & \vdots\\ a(p-1)+1 & a(p-1)+2 & \cdots & ap \end{array} \]那么每一行与a互质的数有 \(\varphi(a)\) 个，共p行，则 \(\varphi(a\times p) = \varphi(a) \times p\) 。
非常感谢Hongse_Fox大佬的思路
实现：
int phi[N+10]; // phi值
int prime[N+10]; // 质数表
bool flag[N+10]; // 是否是质数
int cnt=0; // 质数个数
template<typename T>
void euler_phi(T n){
phi[1]=1; // 1需特判
for(T i=2;i<=n;i++){
if(flag[i]==false){ // 是质数
prime[++cnt]=i;
phi[i]=i-1; // case 1
}
for(T j=1;j<=cnt && prime[j]*i<=n;j++){
flag[i*prime[j]]=true;
if (i%prime[j]==0){ // 是倍数，以后一定还会再遇到，就退出
phi[i*prime[j]]=phi[i]*prime[j]; // case 3
break;
}
phi[i*prime[j]]=phi[i]*phi[prime[j]]; // case 2
}
}
}
例题#1
题目大意
每行输入一个正整数 \(n \leq 1,000,000,000\) ，输出它的欧拉函数值。当 \(n=0\) 时，程序结束。
因为n过大，故我们算一个求一个，使用 good_phi ：
#include<cstdio>
#define ll long long
ll n;
ll phi(ll n){
ll res=n;
for(ll i=2;i*i<=n;i++){
if(n%i==0){
res-=(res/i);
}
while(n%i==0) n/=i;
}
if(n!=1) res-=(res/n);
return res;
}
int main(){
while(true){
scanf("%lld",&n);
if(n==0) break;
printf("%lld\n",phi(n));
}
return 0;
}
例题#2
题目大意
第一行给出数据组数 \(t\leq 10,000\) ，接下来每行输入一个正整数 \(n \leq 32,768\) ，输出它的欧拉函数值。
询问量较大，且n的大小较小，故可以用欧拉筛法求欧拉函数：
#include<cstdio>
#define N 32768
int t,n;
int prime[N+10];
bool flag[N+10];
int phi[N+10];
int cnt;
void euler_phi(){
phi[1]=1;
for(int i=2;i<=N;i++){
if(flag[i]==false){
phi[i]=i-1;
prime[++cnt]=i;
}
for(int j=1;j<=cnt && i*prime[j]<=N;j++){
flag[i*prime[j]]=true;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
int main(){
scanf("%d",&t);
euler_phi();
for(int i=1;i<=t;i++){
scanf("%d",&n);
printf("%d\n",phi[n]);
}
return 0;
}