欧拉函数和欧拉定理
欧拉函数
欧拉函数$\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\pmod m$。其中$\varphi$是欧拉函数。
扩展欧拉定理：对于任意正整数$x$、$m$与某个非负整数$b$，若$b\geq \phi(m)$，那么一定满足$x^b\pmod m=x^{b\pmod{\varphi(m)}+\varphi(m)}\pmod m$
命题1：给定两个互质的数$x$，$p$，记$n$是最小的满足$x^n=1\pmod p$的指数，那么若有$x^m=1\pmod 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\pmod p\]同理：
\[(x^{\frac{t}{k}})^{v}=1\Rightarrow x^{\frac{tv}{k}}=1\pmod 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\pmod 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\pmod 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)$，总的时间复杂度还需要加上预处理欧拉函数的时间。
给一道题目。
一化指数
给定自然数$p$，和另外一个数$x$，满足$1\leq x<p$。
找到最小的正整数$k$，满足$x^k=1\pmod{p}$。称$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\leq x<p$，记这个值为$f(k)$。
我们可以找到任意一个$p$的原根$g$，并且原根一定存在。之后$g^{tk}=1$可以推出$\varphi(p)\mid tk$。而最小的$t$为$\frac{\varphi(p)}{gcd(\varphi(p), k)}$。$t$的取值范围为$1$到$p-1$，故答案为$f(k)=\frac{p-1}{\frac{\varphi(p)}{gcd(\varphi(p), k)}}$，考虑到$p-1=\varphi(p)$，因此有$f(k)=gcd(p-1,k)$。
提供一些题目：