欧拉函数和欧拉定理

Published: by Creative Commons Licence

  • Tags:

欧拉函数

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

欧拉函数的通项公式:

\[\varphi(x)=x\prod_{i=1}^k(1-\frac{1}{p_i})\]

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

从通项公式中可以得出:

\[\varphi(ab)=\frac{\varphi(a)\varphi(b)g}{\varphi(g)}\]

其中$g=gcd(a,b)$。

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

欧拉函数的特殊性质:

\[\sum_{d|n}\varphi(d)=n\]

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

现在我们考虑$S(i)$,其表示由$ki$所形成的集合,其中$k$与$\frac{n}{i}$互质,因此我们可以发现$S(i)=\varphi(\frac{n}{i})$。套入之前的公式可以得到:

\[\sum_{d|n}\varphi(d)=\sum_{d|n}S(i)=n\]

题目$1$:给定$n$,要求计算$\varphi(n)$,其中$1\leq n\leq 10^{18}$。

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

欧拉定理

欧拉定理:若正整数$x$与$m$互质,那么一定有$x^{\varphi(m)}=1\mod m$。其中$\varphi$是欧拉函数。

扩展欧拉定理:对于任意正整数$x$、$m$与某个非负整数$b$,若$b\geq m$,那么一定满足$x^b\mod m=x^{(b\mod \varphi(m))+\varphi(m)}\mod m$

命题1:给定两个互质的数$x$,$p$,记$n$是最小的满足$x^n=1\mod p$的指数,那么若有$x^m=1\mod p$,则一定满足$n\mid m$

证明:

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

\[x^{m-n}x^n=x^m=1\\ \Rightarrow x^{m-n}=1\]

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

命题2:若$t$是$x$的最小归1指数,那么对于任意$k\mid t$,都至少存在一个正整数$y$,满足$k$是$y$的最小归一整数

证明:

\[x^t=1\Rightarrow (x^{\frac{t}{k}})^{k}=1\mod p\]

同理:

\[(x^{\frac{t}{k}})^{v}=1\Rightarrow x^{\frac{tv}{k}}=1\mod p\]

由于$\frac{tv}{k}\geq t$,因此一定有$v\geq k$,故$k$是$x^{\frac{t}{k}}$的最小归一指数。

问题1:给定$n$个数$a_1,a_2,\ldots,a_n$,要求对于$1\leq i\leq n$,计算$\varphi(a_i)$

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

我们可以$O(\sqrt{a_i})$时间复杂度内找到$a_i$的所有素因子,之后根据欧拉函数是积性函数的特质直接$O((\log_2a_i)^2)$时间复杂度内算出$\varphi(a_i)$。总的时间复杂度为$n\sqrt{M}$,其中$M=\max(a_1,a_2,\ldots,a_n)$。

上面的方式可以用Pollard Rho算法替代,这样时间复杂度就能优化到$nM^{\frac{1}{4}}\log_2M$。

问题2:给定两个互质的整数$n$和$x$,要求对所有$n$的因子$d$,计算最小的正整数$m_d$,满足$x^{m_d}=1\mod d$,其中$x<n\leq 10^{14}$

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

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

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

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

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

\[\varphi(x)=x\prod_{i=1}^k(1-\frac{1}{p_i})\]

这也说明了$n$及其所有因子的欧拉函数的值可能的素因子为:$p_1,p_2,\ldots, p_k$,以及$p_1-1,p_2-1,\ldots, p_k-1$分解出的所有质因子,这样质因子总数仅为$P^2+P$个,是相当有限的。

这里我们还需要证明一下分解$p_1-1,p_2-1,\ldots, p_k-1$需要的时间复杂度。

\[\sum_{i=1}^k\sqrt{p_k}\leq \prod_{i=1}^k\sqrt{p_k}=\sqrt{m}\]

第一种方式的时间复杂度为$O(\sqrt{n}+D^2)$,第二种方式的时间复杂度为$O(\sqrt{n}+D(P+\log_2 n)$。还是非常快的。

问题3:给定任意两个正整数$a,m$,以及一个非负整数$b$,要求计算$a^b\mod m$。其中$a,m\leq 10^9,b\leq 10^{20000000}$

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

给一道题目

问题4:给定$n$个数$a_1,a_2,\ldots,a_n$,以及$q$个请求,每个请求给定左右边界$l_i,r_i$和数值,要求计算$a_l^{a_{l+1}^{\ldots ^{a_r}}}$

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

但是实际上你会发现一个非常重要的性质,我们在处理$a_l^x$时使用的模数是$\varphi(m)$,而在处理$a_{l+1}^x$时使用的模数是$\varphi^2(m)$,之后的同理。

而欧拉函数的定义为$\varphi(x)=x\prod_{i=1}^k(1-\frac{1}{p_i})$。当$x$不是偶数的时候,一定有$\varphi(x)\leq x\cdot \frac{1}{2}$,而当$x$不是偶数的时候,这说明其素因子都是奇数,那么$2\mid p_i - 1 \mid \varphi(x)$,即$\varphi(x)$是偶数,因此有$\varphi^2(x)\leq \varphi(x)\cdot \frac{1}{2}$,总结就是$\varphi^2(x)\leq \frac{x}{2}$。

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

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

给一道题目