欧拉函数
在数论,对正整数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;
}
标签:phi,函数,gcd,质数,varphi,times,互质,欧拉,性质
From: https://www.cnblogs.com/znpdco/p/17429367.html