欧拉函数和欧拉定理
欧拉函数
欧拉函数φ(x)表示的是小于等于x的正整数中与x互质的数的数目,特别的是φ(1)=1。
欧拉函数的通项公式:
φ(x)=xk∏i=1(1−1pi)这个可以通过概率简单证明:给定n,对于两个n的不同素因子a,b,从[1,n]中随机挑选一个整数x,记A表示x能整除a,而B表示x能整除b,可以发现A与B是独立事件。我们可以简单扩展得到,对于所有n的素因子其是否能被n整除是相互独立事件,因此p(gcd(x,n)=1)=∏p|n(1−1p)。
从通项公式中可以得出:
φ(ab)=φ(a)φ(b)gφ(g)其中g=gcd(a,b)。
容易发现欧拉函数是积性函数,因此可以用线性筛直接处理。
欧拉函数的特殊性质:
∑d|nφ(d)=n这个性质的证明方式如下:我们将1到n的所有整数,根据他们与n的最大公约数进行分组。记S(i)表示最大公约数为i的所有整数形成的集合的大小,可以发现∑d|nS(d)=n。
现在我们考虑S(i),其表示由ki所形成的集合,其中k与ni互质,因此我们可以发现S(i)=φ(ni)。套入之前的公式可以得到:
∑d|nφ(d)=∑d|nS(i)=n题目1:给定n,要求计算φ(n),其中1≤n≤1018。
考虑到φ(n)是积性函数,因此如果我们能对n进行因式分解
欧拉定理
欧拉定理:若正整数x与m互质,那么一定有xφ(m)=1(modm)。其中φ是欧拉函数。
扩展欧拉定理:对于任意正整数x、m与某个非负整数b,若b≥ϕ(m),那么一定满足xb(modm)=xb(modφ(m))+φ(m)(modm)
命题1:给定两个互质的数x,p,记n是最小的满足xn=1(modp)的指数,那么若有xm=1(modp),则一定满足n∣m
证明:
假如m不能整除n,那么可以推出:
xm−nxn=xm=1⇒xm−n=1这其实就类似于辗转相除法,我们可以能得出xgcd(m,n)=1,考虑到gcd(m,n)<n,这与n是最小的归1指数相悖,因此假设不成立。
命题2:若t是x的最小归1指数,那么对于任意k∣t,都至少存在一个正整数y,满足k是y的最小归一整数
证明:
xt=1⇒(xtk)k=1(modp)同理:
(xtk)v=1⇒xtvk=1(modp)由于tvk≥t,因此一定有v≥k,故k是xtk的最小归一指数。
问题1:给定n个数a1,a2,…,an,要求对于1≤i≤n,计算φ(ai)
这题实际上要求我们计算欧拉函数。下面说几种我知道的计算方式:
我们可以O(√ai)时间复杂度内找到ai的所有素因子,之后根据欧拉函数是积性函数的特质直接O((log2ai)2)时间复杂度内算出φ(ai)。总的时间复杂度为n√M,其中M=max(a1,a2,…,an)。
上面的方式可以用Pollard Rho算法替代,这样时间复杂度就能优化到nM14log2M。
问题2:给定两个互质的整数n和x,要求对所有n的因子d,计算最小的正整数md,满足xmd=1(modd),其中x<n≤1014
很显然我们可以利用欧拉函数计算。
我们先对n进行因式分解,算出所有因子和素因子。现在对于某个因子d,我们要计算md。
一种显然的想法就是遍历所有md的因子,并判断是否可以满足条件。这样的话时间复杂度为O(D2),其中D表示n的因子数。这种做法是可以的,因为可以证明D≤20000。
下面我们来考虑另外一种更有趣的做法。很显然我们可以从任意某个x的归1指数除去一些因子得到最小归1指数(命题1),这意味着我们可以遍历所有d的素因子,并尝试除去这些素因子,如果除去后仍然是归1因子,我们就真的除去,否则恢复。这是一个贪心过程,可以证明最多发生P+log2d次尝试,P是n以内的数最多拥有的素因子数。
上面方法还剩下一个问题,如何对欧拉函数分解所有质因数呢。欧拉函数的定义为:
φ(x)=xk∏i=1(1−1pi)这也说明了n及其所有因子的欧拉函数的值可能的素因子为:p1,p2,…,pk,以及p1−1,p2−1,…,pk−1分解出的所有质因子,这样质因子总数仅为P2+P个,是相当有限的。
这里我们还需要证明一下分解p1−1,p2−1,…,pk−1需要的时间复杂度。
k∑i=1√pk≤k∏i=1√pk=√m第一种方式的时间复杂度为O(√n+D2),第二种方式的时间复杂度为O(√n+D(P+log2n)。还是非常快的。
问题3:给定任意两个正整数a,m,以及一个非负整数b,要求计算ab(modm)。其中a,m≤109,b≤1020000000
当b<m时,我们可以直接快速幂带走。现在考虑当b≥m时,我们可以先计算出φ(m),之后利用扩展欧拉定理对b取模即可。
给一道题目。
问题4:给定n个数a1,a2,…,an,以及q个请求,每个请求给定左右边界li,ri和数值,要求计算aa…arl+1l
由于指数很大,所以我们势必会用到扩展欧拉定理。但是我们发现指数的性质下无法使用倍增之类的预处理技术。
但是实际上你会发现一个非常重要的性质,我们在处理axl时使用的模数是φ(m),而在处理axl+1时使用的模数是φ2(m),之后的同理。
而欧拉函数的定义为φ(x)=x∏ki=1(1−1pi)。当x不是偶数的时候,一定有φ(x)≤x⋅12,而当x不是偶数的时候,这说明其素因子都是奇数,那么2∣pi−1∣φ(x),即φ(x)是偶数,因此有φ2(x)≤φ(x)⋅12,总结就是φ2(x)≤x2。
这意味着我们可以暴力回答每个请求,且每个请求仅前2log2m个元素会对结果产生影响,而后面的的所有指数都会被模上1,即结果总是0。
回答每个请求的时间复杂度为O(log2m),总的时间复杂度还需要加上预处理欧拉函数的时间。
给一道题目。
一化指数
给定自然数p,和另外一个数x,满足1≤x<p。
找到最小的正整数k,满足xk=1(modp)。称k为x的最小一化指数。很显然所有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,满足1≤x<p,记这个值为f(k)。
我们可以找到任意一个p的原根g,并且原根一定存在。之后gtk=1可以推出φ(p)∣tk。而最小的t为φ(p)gcd(φ(p),k)。t的取值范围为1到p−1,故答案为f(k)=p−1φ(p)gcd(φ(p),k),考虑到p−1=φ(p),因此有f(k)=gcd(p−1,k)。
提供一些题目: