0.概述

用来解决幂取模的问题。

1.定理

1.1.基础版

当 $a,p$ 互质时，我们有

$$a^{\phi (p)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

理由是，称所有与 $p$ 互质的数组成的集合为 $S$（即 $S=\{x\in [1,p]|\gcd (x,p)=1\}$），则

$$\{ra\mathrm{m}\mathrm{o}\mathrm{d}p|r\in S\}=S$$

因为 $\gcd (ra,p)=1$ 且两两不同。若 $r_{1}a\equiv r_{2}a$ 则 $r_1\equiv r_2(\mathrm{m}\mathrm{o}\mathrm{d}p)$ ，而这是荒谬的。

于是

$$\prod _{r\in S}(ra)\equiv \prod _{r\in S}r(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

左式显然等于 $a^{\phi (p)}{\prod }_{r\in S}r$ ，因为 $S$ 的大小是 $\phi (p)$ 。于是乎

$$a^{\phi (p)}\prod _{r\in S}r\equiv \prod _{r\in S}r(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

而 ${\prod }_{r\in S}r$ 与 $p$ 互质，可以消去。剩下的就是

$$a^{\phi (p)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

1.2.升级版

对于任意 $a,p,x(\phi (p)\le x)$ 满足

$$a^x\equiv a^{x\mathrm{m}\mathrm{o}\mathrm{d}\phi (p)}\cdot a^{\phi (p)}(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

理由是精妙的。首先说明这一点：对于任意质数 $p$ 和正整数 $q$ 满足 $\phi (p^q)\ge q$ 。构造法即可：此 $q$ 个数为 $p^i-1$（$i$ 取 $1,2,3,\dots ,q$ 就恰好有 $q$ 个）。然后小分类讨论：

互质的情况。

当 $\gcd (a,p)=1$ 时，就是 1.1.基础版 的情形，故成立。

不互质的情况。

当 $p$ 只有一个质因子时，设 $p=q^k$ ，因为 $\gcd (a,p)\ne 1$ ，所以 $a$ 也同样含有此质因子。而 $x\ge \phi (p)=\phi (q^k)\ge k$ ，所以 $q^k|a^x$ 。所以

$$a^x\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

这是对 $\forall x\ge \phi (p)$ 都成立的。而 $x\mathrm{m}\mathrm{o}\mathrm{d}\phi (p)+\phi (p)$ 显然也是一个合法的 $x$ 取值。于是

$$a^x\equiv a^{x\mathrm{m}\mathrm{o}\mathrm{d}\phi (p)}\cdot a^{\phi (p)}(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

其实两边都是零，蠢透了。

当 $p$ 不只有一个质因子时，设 $p=q_1^{k_1}{q}_2^{k_2}\cdots q_n^{k_n}$ 为其质因数分解，记 $p_i=q_i^{k_i}$ 。由于 $x\ge \phi (p)\ge \phi (p_i)$ ，肯定有

$$a^x\equiv a^{x\mathrm{m}\mathrm{o}\mathrm{d}\phi (p_i)}\cdot a^{\phi (p_i)}(\mathrm{m}\mathrm{o}\mathrm{d}{p}_i)$$

而这个式子的本质是什么？是 $a^{\phi (p_i)}\equiv a^{2\phi (p_i)}$ 。没看出来充分，至少看出来其必要。

两边都变成原来的 ${\prod }_{j\ne i}\phi (p_j)$ 次方，取模意义下等式仍成立。故

$$a^{\phi (p)}\equiv a^{2\phi (p)}(\mathrm{m}\mathrm{o}\mathrm{d}{p}_i)$$

因为 ${\prod }_{j=1}^n\phi (p_j)=\phi (p)$ ，积性函数嘛。

注意到 $x,y$ 如果在模 $a$ 和模 $b$ 意义下都相等，那二者在模 $\text{lcm}(a,b)$ 意义下亦相等。于是得到

$$a^{\phi (p)}\equiv a^{2\phi (p)}(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

而上式是充分的，自行验证不难。结论即是开头的式子。

2.例题

2.1.板题

2.1.1.题目

$\mathtt{C}\mathtt{a}\mathtt{l}\mathtt{c}\mathtt{u}\mathtt{l}\mathtt{a}\mathtt{t}\mathtt{i}\mathtt{o}\mathtt{n}$：定义 $f(n)=(n\mathrm{m}\mathrm{o}\mathrm{d}10{)}^{f(\lfloor \frac{n}{10}\rfloor )}$ ，边界为 $f(0)=1$ ，求 $f(n)\mathrm{m}\mathrm{o}\mathrm{d}m$ 。$n,m\le 10^9$ 。

2.1.2.思路

显然唯一问题就是 $f$ 的值很大。利用欧拉降幂即可。怎么判断 $f(n)$ 的指数是否超过了 $\phi (m)$ 呢？

注意到 $a^{\phi (p)}\equiv a^{2\phi (p)}$ 这个式子中，两边的值明显不同（除非 $a\le 1$ ，因为 $\phi (p)=0$ 恒不成立）。如果要相等，则右式一定超过了模数。故

$$a^{2\phi (p)}\ge p$$

注意 $a^{\phi (p)}\ge p$ 未必成立。比如 $\phi (6)=2$ 就会被 $a=2$ 绝杀。

于是用 $f(n,m)$ 表示 $f(n)$ （题面中的那个）取模 $m$ 的值。$g(n,m)$ 表示 $f(n)$ 是否不小于 $m$ 。有递推式

$$f(n,m)=(n\mathrm{m}\mathrm{o}\mathrm{d}10{)}^{f[\lfloor \frac{n}{10}\rfloor ,\phi (m)]+g[\lfloor \frac{n}{10}\rfloor ,\phi (m)]\cdot \phi (m)}\mathrm{m}\mathrm{o}\mathrm{d}m$$

$$g(n,m)=f(n,m)\vee g\left[\lfloor \frac{n}{10}\rfloor ,2\phi (m)\right]$$

第二个式子中的 $f(n,m)$ 大家都懂的，就是计算过程中超过了 $m$ 就行。但是两个式子的递归情况不同，比较烦。因为我们必须保证 $g(n,m)$ 中涵盖了两种情况——递归中取模了；未取模，幂时爆了。

但是我们有妙招：在 $g(n,2m)=1$ 时，$f(n,m)+g(n,m)\cdot m=f(n,2m)\mathrm{m}\mathrm{o}\mathrm{d}m+m$ ；在 $g(n,2m)=0$ 时，$f(n,m)+g(n,m)\cdot m=f(n,2m)$ 。

所以 $f(n,m)$ 的方程式中的指数可以被完全表示出来了，只递归 $2\phi (m)$ 的情况即可。

2.1.3.代码

#include <cstdio> #include <iostream> #include <vector> using namespace std; typedef long long int_; inline int readint(){ int a = 0; char c = getchar(), f = 1; for(; c<'0'||c>'9'; c=getchar()) if(c == '-') f = -f; for(; '0'<=c&&c<='9'; c=getchar()) a = (a<<3)+(a<<1)+(c^48); return a*f; } int_ getphi(int_ n){ int_ res = n; for(int i=2; i<=n/i; ++i) if(n%i == 0){ res = res/i*(i-1); while(!(n%i)) n /= i; } if(n > 1) res = res/n*(n-1); return res; } int_ mul(int_ a,int_ b,int_ c){ // int_ sysl = (a*b-(int_)((long double)a/c*b+1e-8)*c)%c; // if(sysl < 0) sysl += c; return sysl; int_ ans = 0; if(a < b) swap(a,b); for(; b; b>>=1,a=(a<<1)%c) if(b&1) ans = (ans+a)%c; return ans; } bool over; // 是否超出过 m int_ qkpow(int_ bas,int_ q,int_ m){ int_ ans = 1; bool zxy = 0; for(; q; q>>=1){ if(q&1){ if(bas && ans > (m-1)/bas) over = true; if(zxy) over = true; ans = mul(ans,bas,m); } if(bas && bas > (m-1)/bas) zxy = true; bas = mul(bas,bas,m); } return ans; } int_ f(int n,int_ m){ if(n == 0){ over = 0; // 多组数据！ return 1; // 题面中的规定 } if(n%10 == 1){ over = 0; return 1; } if(!(n%10)){ if(f(n/10,m) || over){ over = 0; return 0; } return 1; // 0^0 = 1 } int_ phi = getphi(m); int_ x = f(n/10,phi<<1); if(over) x = x%phi+phi; return qkpow(n%10,x,m); } int main(){ int T, n, m; for(scanf("%d",&T); T; --T){ scanf("%d %d",&n,&m); printf("%lld\n",f(n,m)); } return 0; }

2.1.4.后记

搜到的题解中还有另一种做法，就是认为 $a^{\phi (p)}\ge p$ ，故而直接求 $f(n,m)+g(n,m)\cdot m$ 的值，$g$ 只在计算幂时考虑，不递推。

为什么这是对的呢？因为 我太敏感一来就找到反例 只有 $2^{\phi (6)}<6$ 。只有 $6$ 能做到！

如果要构造反例，则需要 $\phi (p)=6$ ，故 $p\in \{7,9,14,18\}$ 。但这几个模数都无法构造出反例。

所以究竟为什么只有 6 满足这个式子啊，淦。

有些题解是完全错误的，只需要试试 $f(253)\mathrm{m}\mathrm{o}\mathrm{d}36$ 就能找出问题。答案应当为 $27$ 。

这道题中的 $0^0=1$ 的规定也非常不友好。我因为这一条 $\mathtt{W}\mathtt{A}$ 了十几发。

2.2.狗题

2.2.1.题目

相逢是问候：区间修改，$a^{\prime }=a^c$ ；区间查询 $\sum a$ 。这里的 $c$ 是固定不变的，即，每次修改操作都是同一个 $c$ 。$1\le n,m\le 5\times 10^4,1\le c<p\le 10^8$ 。

2.2.2.思路

不难发现一个数就会变成 $c^{c^{c^a}}$ 。当层数够大，足以让 $a$ 无用时（某一层的 $\phi =1$ 了），这个数就不会变。用并查集去找到每一个没有“堆叠够高”的数字并暴力修改。每个数字会被修改 $\mathcal{O}(\log p)$ 次。由于每次都要重新将数字塔拆开（或者你存储当前数字的 $\mathcal{O}(\log p)$ 种余数），所以一次修改需要做 $\mathcal{O}(\log p)$ 求 $c^y$ 的工作。没办法，只好使用光速乘。

总复杂度 $\mathcal{O}(n{\log }^{2}p+n\log p\log n+\sqrt{p}+m\log n)$ 。并查集的复杂度我也不太清楚，我按照 $m\log n$ 算的。

2.2.3.代码

然后咕掉了。