欧拉函数和欧拉定理

Published: by Creative Commons Licence

  • Tags:

欧拉函数

欧拉函数φ(x)表示的是小于等于x的正整数中与x互质的数的数目,特别的是φ(1)=1

欧拉函数的通项公式:

φ(x)=xki=1(11pi)

这个可以通过概率简单证明:给定n,对于两个n的不同素因子a,b,从[1,n]中随机挑选一个整数x,记A表示x能整除a,而B表示x能整除b,可以发现AB是独立事件。我们可以简单扩展得到,对于所有n的素因子其是否能被n整除是相互独立事件,因此p(gcd(x,n)=1)=p|n(11p)

从通项公式中可以得出:

φ(ab)=φ(a)φ(b)gφ(g)

其中g=gcd(a,b)

容易发现欧拉函数是积性函数,因此可以用线性筛直接处理。

欧拉函数的特殊性质:

d|nφ(d)=n

这个性质的证明方式如下:我们将1n的所有整数,根据他们与n的最大公约数进行分组。记S(i)表示最大公约数为i的所有整数形成的集合的大小,可以发现d|nS(d)=n

现在我们考虑S(i),其表示由ki所形成的集合,其中kni互质,因此我们可以发现S(i)=φ(ni)。套入之前的公式可以得到:

d|nφ(d)=d|nS(i)=n

题目1:给定n,要求计算φ(n),其中1n1018

考虑到φ(n)是积性函数,因此如果我们能对n进行因式分解

欧拉定理

欧拉定理:若正整数xm互质,那么一定有xφ(m)=1(modm)。其中φ是欧拉函数。

扩展欧拉定理:对于任意正整数xm与某个非负整数b,若bϕ(m),那么一定满足xb(modm)=xb(modφ(m))+φ(m)(modm)

命题1:给定两个互质的数xp,记n是最小的满足xn=1(modp)的指数,那么若有xm=1(modp),则一定满足nm

证明:

假如m不能整除n,那么可以推出:

xmnxn=xm=1xmn=1

这其实就类似于辗转相除法,我们可以能得出xgcd(m,n)=1,考虑到gcd(m,n)<n,这与n是最小的归1指数相悖,因此假设不成立。

命题2:若tx的最小归1指数,那么对于任意kt,都至少存在一个正整数y,满足ky的最小归一整数

证明:

xt=1(xtk)k=1(modp)

同理:

(xtk)v=1xtvk=1(modp)

由于tvkt,因此一定有vk,故kxtk的最小归一指数。

问题1:给定n个数a1,a2,,an,要求对于1in,计算φ(ai)

这题实际上要求我们计算欧拉函数。下面说几种我知道的计算方式:

我们可以O(ai)时间复杂度内找到ai的所有素因子,之后根据欧拉函数是积性函数的特质直接O((log2ai)2)时间复杂度内算出φ(ai)。总的时间复杂度为nM,其中M=max(a1,a2,,an)

上面的方式可以用Pollard Rho算法替代,这样时间复杂度就能优化到nM14log2M

问题2:给定两个互质的整数nx,要求对所有n的因子d,计算最小的正整数md,满足xmd=1(modd),其中x<n1014

很显然我们可以利用欧拉函数计算。

我们先对n进行因式分解,算出所有因子和素因子。现在对于某个因子d,我们要计算md

一种显然的想法就是遍历所有md的因子,并判断是否可以满足条件。这样的话时间复杂度为O(D2),其中D表示n的因子数。这种做法是可以的,因为可以证明D20000

下面我们来考虑另外一种更有趣的做法。很显然我们可以从任意某个x的归1指数除去一些因子得到最小归1指数(命题1),这意味着我们可以遍历所有d的素因子,并尝试除去这些素因子,如果除去后仍然是归1因子,我们就真的除去,否则恢复。这是一个贪心过程,可以证明最多发生P+log2d次尝试,Pn以内的数最多拥有的素因子数。

上面方法还剩下一个问题,如何对欧拉函数分解所有质因数呢。欧拉函数的定义为:

φ(x)=xki=1(11pi)

这也说明了n及其所有因子的欧拉函数的值可能的素因子为:p1,p2,,pk,以及p11,p21,,pk1分解出的所有质因子,这样质因子总数仅为P2+P个,是相当有限的。

这里我们还需要证明一下分解p11,p21,,pk1需要的时间复杂度。

ki=1pkki=1pk=m

第一种方式的时间复杂度为O(n+D2),第二种方式的时间复杂度为O(n+D(P+log2n)。还是非常快的。

问题3:给定任意两个正整数a,m,以及一个非负整数b,要求计算ab(modm)。其中a,m109,b1020000000

b<m时,我们可以直接快速幂带走。现在考虑当bm时,我们可以先计算出φ(m),之后利用扩展欧拉定理对b取模即可。

给一道题目

问题4:给定n个数a1,a2,,an,以及q个请求,每个请求给定左右边界li,ri和数值,要求计算aaarl+1l

由于指数很大,所以我们势必会用到扩展欧拉定理。但是我们发现指数的性质下无法使用倍增之类的预处理技术。

但是实际上你会发现一个非常重要的性质,我们在处理axl时使用的模数是φ(m),而在处理axl+1时使用的模数是φ2(m),之后的同理。

而欧拉函数的定义为φ(x)=xki=1(11pi)。当x不是偶数的时候,一定有φ(x)x12,而当x不是偶数的时候,这说明其素因子都是奇数,那么2pi1φ(x),即φ(x)是偶数,因此有φ2(x)φ(x)12,总结就是φ2(x)x2

这意味着我们可以暴力回答每个请求,且每个请求仅前2log2m个元素会对结果产生影响,而后面的的所有指数都会被模上1,即结果总是0

回答每个请求的时间复杂度为O(log2m),总的时间复杂度还需要加上预处理欧拉函数的时间。

给一道题目

一化指数

给定自然数p,和另外一个数x,满足1x<p

找到最小的正整数k,满足xk=1(modp)。称kx的最小一化指数。很显然所有x的一化指数都能整除它的最小一化指数。

首先如果gcd(x,p)>1,那么k一定不存在。我们可以始终认为x,p互质。根据欧拉定理可以得知$$k| \varphi(p)$。我们可以尝试所有的$\varphi(p)$的因子,时间复杂度约为$O(p^{1/3}\log_2p)$,但是实际上我们不断枚举素因子并删除的话,可以优化到$O((\log_2p)^2)$。

接下来考虑另外一个问题,给定k,判断存在多少个数x,满足1x<p,记这个值为f(k)

我们可以找到任意一个p的原根g,并且原根一定存在。之后gtk=1可以推出φ(p)tk。而最小的tφ(p)gcd(φ(p),k)t的取值范围为1p1,故答案为f(k)=p1φ(p)gcd(φ(p),k),考虑到p1=φ(p),因此有f(k)=gcd(p1,k)

提供一些题目: