浅谈欧拉函数[通俗易懂]

浅谈欧拉函数[通俗易懂]前言欧拉函数听起来很高大上,但其实非常简单,也是NOIP里的一个基础知识,希望大家看完我的博客能有所理解。什么是欧拉函数欧拉函数是小于x的正整数中与x互质的数的个数,一般用φ(x)表示。特殊的,φ(1)=1。如何计算欧拉函数通式:φ(x)=x∏ni=1(1−1pi)∏i=1n(1−1pi)\prod_{i=1}^n{(1-\frac{1}{p_i})}φ(1)=1其…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

前言

欧拉函数听起来很高大上,但其实非常简单,也是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=1n(1pi1)
φ(1)=1
其中 p 1 p_1 p1, p 2 p_2 p2…… p n p_n pn为x的所有质因数,x是正整数。
那么,怎么理解这个公式呢?对于x的一个质因数 p i p_i pi,因为x以内 p i p_i pi的倍数是均匀分布的,所以x以内有 1 p i \frac {1}{p_i} pi1的数是 p i p_i pi的倍数,那么有1- 1 p i \frac {1}{p_i} pi1的数不是 p i p_i pi的倍数。再对于 p j p_j pj,同理,有1- 1 p j \frac {1}{p_j} pj1的数不是 p j p_j pj的倍数,所以有 ( 1 − 1 p i ) ∗ ( 1 − 1 p j ) (1-\frac {1}{p_i})*(1-\frac {1}{p_j}) (1pi1)(1pj1)的数既不是 p i p_i pi的倍数,又不是 p j p_j pj的倍数。最后就有 ∏ i = 1 n ( 1 − 1 p i ) \prod_{i=1}^n{(1-\frac{1}{p_i})} i=1n(1pi1)的数与x互质,个数自然就是x ∏ i = 1 n ( 1 − 1 p i ) \prod_{i=1}^n{(1-\frac{1}{p_i})} i=1n(1pi1)
还不理解?没关系,举个例子。比如x=12,12以内有 1 2 \frac {1}{2} 21的数是2的倍数,那么有1- 1 2 \frac {1}{2} 21的数不是2的倍数(1,3,5,7,9,11),这6个数里又有 1 3 \frac {1}{3} 31的数是3的倍数,只剩下(1- 1 2 \frac {1}{2} 21)* (1- 1 3 \frac {1}{3} 31)的数既不是2的倍数,也不是3的倍数(1,5,7,11)。这样剩下的 12*(1- 1 2 \frac {1}{2} 21)*(1- 1 3 \frac {1}{3} 31),即4个数与12互质,所以φ(12)=4。

积性函数

先介绍一下什么是积性函数,后面将会用到。若当m与n互质时, f ( m ∗ n ) = f ( m ) ∗ f ( n ) f(m*n)=f(m)*f(n) f(mn)=f(m)f(n),那么f是积性函数。若对任意正整数,都有f(m*n)=f(m)*f(n)成立,则f是完全积性函数。

欧拉函数的几个性质

1.对于质数p, φ ( p ) = p − 1 φ(p)=p-1 φ(p)=p1
2.若p为质数, n = p k n=p^k n=pk,则 φ ( n ) φ(n) φ(n)= p k p^k pk p k − 1 p^{k-1} pk1
3.欧拉函数是积性函数,但不是完全积性函数。若m,n互质,则 φ ( m ∗ n ) = φ ( m ) ∗ φ ( n ) φ(m*n)=φ(m)*φ(n) φ(mn)=φ(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=dnφ(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=1n(1pi1)=x(1p1)=pk(1p1)=pkpk1
3.因为m与n互质,所以它们没有公共的质因数。设m有 a m a_m am个质因数,n有 a n a_n an个质因数。 φ ( 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)=mni=1am(1pi1)i=1an(1pi1)=mni=1am+an(1pi1)=φ(mn)
4.前几个都可以利用公式证明,这个却不行。首先有一个基本事实(我不想证明),若gcd(n,m)=1,则gcd(n,n-m)=1(设n>m)。当m=n-m时, n = 2 ∗ m n=2*m n=2m,那么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)} dnφ(d)。首先证明F(n)是个积性函数:设m,n互质,则要证 F ( m ∗ n ) = F ( m ) ∗ F ( n ) F(m*n)=F(m)*F(n) F(mn)=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)=imφ(i)jnφ(j)=φ(i1)φ(j1)+φ(i1)φ(j2)+...+φ(i2)φ(j1)+φ(i2)φ(j2)+...+φ(ikm)φ(jkn)这里假设 i 1 , i 2 , . . . i k m i_1,i_2,…i_{km} i1,i2,...ikm为m的所有因数, j 1 , j 2 , . . . j k n j_1,j_2,…j_{kn} j1,j2,...jkn为n的所有因数之和,因为m与n互质,所以它们的因数也必然全都两两互质,而欧拉函数又是个积性函数,即 φ ( i k ∗ j k ) = φ ( i k ) ∗ φ ( j k ) φ(i_k*j_k)=φ(i_k)*φ(j_k) φ(ikjk)=φ(ik)φ(jk),那么上式又可以等价于 φ ( 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})。 φ(i1j1)+φ(i1j2)+...+φ(i2j1)+φ(i2j2)+...+φ(ikmjkn)可以发现, 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} i1j1,i1j2,...,i2j1,i2j2,...,ikmjkn这些数构成了 m ∗ n m*n mn的所有因数。那么这些数的欧拉函数之和就等于 F ( m ∗ n ) F(m*n) F(mn),所以 F ( m ∗ n ) = F ( m ) ∗ F ( n ) F(m*n)=F(m)*F(n) F(mn)=F(m)F(n),证得F是一个积性函数。根据这个性质,F可以一直分解到n为质数的幂的情况。那么讨论当p为质数时,F(p^k)怎么计算。因为 p k p^k pk的因数只有 1 , p , p 2 , p 3 , . . . , p k 1,p,p^2,p^3,…,p^k 1,p,p2,p3,...,pk,根据F的定义,直接展开来计算就行了。(根据欧拉函数的性质2,φ( p k p^k pk)= p k − p ( k − 1 ) p^k-p^(k-1) pkp(k1) 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(pk)=φ(1)+φ(p)+φ(p2)+...+φ(pk)=1+(p1)+(p2p)+...+(pkp(k1))=pk既然对于质数的幂,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=1n(1pi1) = x ∏ i = 1 n p i − 1 p i \prod_{i=1}^n{\frac{p_i-1}{p_i}} i=1npipi1 。我们用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) phi[x]=phi[x]/pi(pi1)(先除再乘,避免溢出)。当然,若只要求一个数的欧拉函数,可以从1到sqrt(n)扫一遍,若gcd(i,n)=1就更新 p h i [ n ] phi[n] phi[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=1n(1pk1) =φ(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]];//利用了欧拉函数是个积性函数的性质 
		}
	}
}

总结

有关欧拉函数的性质,只需做个了解,而求欧拉函数的代码,却是一定要会写的。这只是走进数论世界的第一步。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/172048.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 网站备案是域名备案还是服务器备案(域名备案一定要服务器吗)

    网站域名服务器怎么备案内容精选换一换WordPress简称WP,最初是一款博客系统,后逐步演化成一款免费的CMS(内容管理系统/建站系统)。本文档指导用户使用华为云市场镜像“Wordpress官方正式版”部署WordPress博客系统。已购买虚拟私有云和弹性公网IP。如果规划为网站配置域名,需已经购买好相应的域名。弹性云服务器所在安全组添加了如表1所示的安全组规则,具体步骤空壳网站指备案主体已在…

  • 最短路径问题—SPFA算法详解

    最短路径问题—SPFA算法详解前言博客编写人:Willam博客编写时间:2017/3/12博主邮箱:2930526477@qq.com(有志同道合之人,可以加qq交流交流编程心得)1、最短路径问题介绍问题解释:从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径解决问题的算法:迪杰斯特拉算法(Dijkstra算法)弗洛伊德算法(Floyd算法)SPFA…

  • Linode 遭受大规模DDoS攻击

    Linode 遭受大规模DDoS攻击美国当地时间12月29日,专用虚拟服务器提供商Linode遭到DDoS攻击,截至到本文发布时其web服务的访问仍受影响,其中API调用和管理功能依然部分不可用。Linode称正在努力尽快恢复正常访问服务。\\早在2013年就有过Linode就遭到大规模DDoS攻击。在HackNews上的讨论中,有人认为Linode在安全建设方面多有疏忽,并且和ISP缺乏配合,从而导致此次DDoS攻击影响过甚。\…

  • ipv4地址分类_d类ipv4地址以什么开始

    ipv4地址分类_d类ipv4地址以什么开始ipv4地址:表示一个网络节点的网络地址总共可以产生40多亿ip地址,32位二进制数–表示用点分十进制IPv4地址由四段组成,每个字段是一个字节,8位,最大值是255,,IPv4地址由两部分组成,即网络地址和主机地址。网络地址表示其属于互联网的哪一个网络,主机地址表示其属于该网络中的哪一台主机,两者是主从关系。IPv4地址的四大类型标识的是网络中的某台主机。IPv4地址长度为32位,共4…

    2022年10月22日
  • tqdm模块[通俗易懂]

    tqdm模块[通俗易懂]tqdm是Python进度条库。tqdm库下面有2个类我们经常使用:1.2.可以在Python长循环中添加一个进度提示信息用法:tqdm(iterator)trange(i)是

  • tcp四次挥手,为什么是四次?「建议收藏」

    tcp四次挥手,为什么是四次?「建议收藏」四次挥手的原因;为什么要有TIME_WAIT状态?2MSL的的意义;四次挥手中如果有一次挥手失败怎么处理?

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号