(测试)

乘法逆元

定义

数 $a$ 模 $p$ 意义下的乘法逆元($\texttt{Modular Multiplicative Inverse}$)被定义为 线性同余方程 $ax\equiv 1 \pmod p$的解。

条件

$\gcd(a,p)=1$是数 $a$ 在模 $p$ 意义下存在乘法逆元的充分必要条件。

求法

1.扩展欧几里得法

既然乘法逆元是线性同余方程的解，那么使用扩展欧几里得算法$(\texttt{Extended Euclidean algorithm, EXGCD})$求出方程的通解。再经转换即可求出特解。

过程

将同余方程 $ax\equiv 1 \pmod p$ 改写为如下形式

\[\begin{aligned} ax+py &=1 &(1) \end{aligned}\]

其中$x,y$是未知数。显然，这两个方程是等价的。

由裴蜀定理可得，方程$ax\equiv b \pmod p$ 有整数解的充分必要条件是 $\gcd(a,p)\mid 1$ ，且容易将其转换为: $\gcd(a,p)=1$

也就是说，满足如下条件时，才能使用扩展欧几里得算法求解逆元：

\[\gcd(a,p)=1 \]
即需要 $a,p$ 互质。

所以我们可将等式$(1)$再次改写为

\[ax+py=\gcd(a,p) \]

这就化为扩欧求解方程的一般形式 $ax+by=\gcd(a,b)$ 了。接下来使用扩欧求解即可

\[\begin{aligned} \text{设}&:\\ &ax_{1}+py_{1}=\gcd(a,p)\\ &px_2+(a\bmod p)y_2=\gcd(p,a\bmod p)\\ \because&\space\text{由欧几里得定理知}\ \gcd(a,p)=\gcd(p,a\bmod p)\\ \therefore&\space ax_{2}+py_{1}=px_2+(a\bmod p)y_2\\ \because&\space a\bmod p=a-\lfloor\frac{a}{p}\rfloor p\\ \therefore&\space ax_1+py_1=px_2+\left(a-\lfloor\frac{a}{p}\rfloor p\right)y_2\\ \therefore\space &ax_1+py_1=ay_2+p\left(x_2-\lfloor\frac{a}{p}\rfloor y_2\right)\\ \because&\space a=a,p=p\\ \therefore&\space \text{比对法可得}\\ &\begin{cases} x_1=y_2,\\ y_1=x_2-\lfloor\frac{a}{p}\rfloor y_2. \end{cases} \end{aligned}\]

由此我们得到了 $x_1,y_1$ 与 $x_2,y_2$之间的关系，又因为它们都与 $\gcd(a,p)$ 有关，所以只需要将 $x_2,y_2$ 在求$\gcd(a,p)$的过程中一并计算，辗转相除直到 $p_i=0,\gcd(a_i,p_i)=a_i$ 时返回$x_2=1,y_2=0$ 来递归求解即可求出在线性同余方程 $ax\equiv 1 \pmod p$ 中 $x$ 的通解。

求出通解 $x_0$ 后，一个特解(最小正整数解 )即为

\[\begin{aligned} x&=\left(x_0\bmod \frac{p}{\gcd(a,p)}+\frac{p}{\gcd(a,p)}\right)\bmod \frac{p}{\gcd(a,p)}\\ &=\left(x_0\bmod \frac{p}{1}+\frac{p}{1}\right)\bmod \frac{p}{1}\\ &=\left(x_0\bmod p+p\right)\bmod p. \end{aligned}\]

$a$ 在模 $p$ 意义下的乘法逆元即为 $x$ 的值。

实现

以下是扩展欧几里得算法的伪代码

\[\begin{array}{ll} &\textbf{Extended Euclidean algorithm }\operatorname{exgcd}(\mathbf{a}, \mathbf{b}, ⇒{\mathbf{x}}, ⇒\mathbf{y})\text{:} \\ 1 & \textbf{Parameters. } a,b\in\mathbb{Z}^+,b\ne0.\space x \text{ and } y \text{ are bit references}.\\ & \text{Denoting the }a,b,x\text{ and }y\text{ in the equation } \boxed{ax+by=\operatorname{gcd}(a,b)}. \\ &\text{Initialize } x\gets\varnothing,y\gets\varnothing\\ 2 & \textbf{Return value. } \text{The GCD between }a\text{ and }b.\\ & \textbf{Accompanying results }x\text{ and }y \text{ is the solution to the equation}.\\ 3 & \textbf{Method. } \\ 4 & \textbf{if }b=0 \\ 5 & \qquad x\gets1 \\ 6 & \qquad y\gets0\\ 7 & \qquad \textbf{return }\ a \\ 8 & {result}_{{\operatorname{\textbf{(new)}}} }\gets\operatorname{exgcd}\left(b,a\bmod b,x,y\right) \\ & (\texttt{At this point the values of }x\texttt{ and }y\texttt{ have changed}.)\\ 9 & x_{2{\operatorname{\textbf{(new)}}} }\gets x\\ 11 & y_{2{\operatorname{\textbf{(new)}}} }\gets y\\ 12 & x\gets y_2\\ 13 & y\gets x_2-\lfloor\dfrac{a}{b}\rfloor y_2\\ 14 & \textbf{return }\ result\\ \end{array} \]

复杂度

扩展欧几里得算法的时间复杂度与欧几里得算法（辗转相除法）无异，均为

\[\text{O}(\log p) \]

优劣

优势

扩展欧几里得法求解乘法逆元只需满足 $\gcd(a,p)=1,$ 即原数与模数互质即可，而后文提到其他算法均，需另外要求 $p$ 为质数，即模数要为质数。

劣势

扩展欧几里得法求解乘法逆元的过程较为复杂，记忆较困难。
速度：大多使用递归实现辗转相除法，比其他迭代实现的算法常数要高一些，跑得慢。
在求多个数逆元时必须多次运算，复杂度高，所以一般只能用于求出单个数的逆元。

2.快速幂法

当 $\gcd(a,p)=1,$$\boldsymbol{p}$为质数 时,借助费马小定理$(\texttt{Fermat's Little Theorem})$可转化同余方程 $ax\equiv 1 \pmod p$，得其通解 $x_0=a^{p-2}$

过程

\[\begin{aligned} \because&\space\text{当 } p\text{ 为质数时}:\\ &\space a^{p-1}\equiv1{\pmod p}\text{ (费马小定理)}\\ \text{又}&\space ax\equiv 1 \pmod p\\ \therefore&\space ax\equiv a^{p-1}\pmod{p}\\ \because&\space \gcd(a,p)=1\\ \therefore&\space x\equiv a^{p-2}\pmod{p} \end{aligned}\]

然后即可用快速幂求出 $a^{p-2}$ 的值，即求出一个通解 $x_0$ 了

在大部分情况下$,a>0,$ 所以此时 $a^{p-2}>0$ ，求不求特解都无所谓了。

实现

以下是快速幂法求解逆元的伪代码

\[\begin{array}{ll} &\overline{\underline{\textbf{Modular Multiplicative Inverse Solving Algorithm by Exponentiation}}}\\ 1 & \textbf{Fast Power Algorithm } \operatorname{exponentiation}(\mathbf{a},\mathbf{b},\mathbf{p})\text{:}\\ 2 & \textbf{Parameters. } a,b,p\in\mathbb{N}^+.\\ & \text{Denoting the base } a,\text{the exponent }b\text{ and the modulus }p.\\ 3 & \textbf{Returned value. }\text{the value of }\boxed{a^b\bmod{p}}\\ 4 & \textbf{Method.}\\ 5 & {base}_{\operatorname{\textbf{(new)}}}\gets a\\ 6 & result_{\operatorname{\textbf{(new)}}}\gets 1\\ 7 & \textbf{while}\space b>0\space\textbf{do}\\ 8 & \qquad \textbf{if }2\nmid b\textbf{ then}\\ 9 & \qquad \qquad result\gets result\cdot base\bmod{p}\\ 10 & \qquad base\gets {base}^{2}\bmod p\\ 11 & \qquad b\gets\lfloor\dfrac{b}{2}\rfloor\\ 12 & \textbf{end}\\ 13 & \textbf{return } result\\\\ 14 & \textbf{Multiplicative Inverse Solving Algorithm }\text{getInverse(\textbf{a},\textbf{p}):}\\ 15 & \textbf{Parameters. } a,p\in\mathbb{N}^+,a\ne 0,\gcd(a,p)=1,p\text{ is a prime}.\\ & \text{Denoting the coefficient } a\text{ and the modulus }p \text{ in the congruence equation}\boxed{ax\equiv 1\pmod{p}}.\\ 16 & \textbf{Returned value. }\text{the modular multiplicative inverse of $a$: }\space a^{-1},\\ & \text{which is the solution to the congruence equation}\boxed{ax\equiv 1\pmod{p}}.\\ 17 & \textbf{Method.}\\ 18 & result_{\operatorname{\textbf{({new})}}}\gets\operatorname{exponentiation}(a,p-2,p)\bmod{p}\\ & \textbf{return }result \end{array} \]

复杂度

快速幂求逆元的复杂度就是快速幂的复杂度，即

\[\text{O}(\log p) \]

优劣

优势

快速幂法求逆元十分容易记忆理解，代码难度小。使用迭代实现快速幂，常数小。

劣势

局限性：只能用于求模数为质数情况下的逆元，局限性较大。
还是只在求单个数逆元时快。

3.线性迭代法

为求出$1,2,\dots,n$这$n$个数中每个数 $a$ 在模 $p$ 意义下的逆元 $a^{-1}$ ，上文两种方法就很慢了，我们需要使用线性方法在$\text{O}(n) $复杂度内求出每个数的逆元才不会超时。

过程

\[\begin{aligned} &\space \text{对于正整数 }a\ (1\leq a\leq n),\text{有}\\ &\space p=a\lfloor\frac{p}{a}\rfloor+p\bmod a\\ \because&\space p\equiv 0\pmod{p}\\ \therefore&\space a\lfloor\frac{p}{a}\rfloor+p\bmod a\equiv 0\pmod{p}\\ &\space \text{将同余式两边同时乘以 }a^{-1}(p\bmod a)^{-1}\text{得到}\\ &\space \lfloor\frac{p}{a}\rfloor\left(p\bmod a\right)^{-1}+a^{-1}\equiv 0\pmod{p}\\ \therefore&\space a^{-1}\equiv - \lfloor\frac{p}{a}\rfloor\left(p\bmod a\right)^{-1}\pmod{p}\\ \because&\space \text{显然 }1^{-1}\equiv 1\pmod p,\text{且 }p\bmod a< a\\ &\space \text{也就是说，正向递推求解$a^{-1}$是可行的.}\\ \therefore&\space \text{可得出从$a=1$开始，$a^{-1}$的递推式}:\\ &\space a^{-1}\equiv\begin{cases} 1&\text{if }a=1,\\ -\lfloor\dfrac{p}{a}\rfloor\left(p\bmod a\right)^{-1}&\text{otherwise.} \end{cases} \end{aligned}\]

这样我们在已经迭代求出所有$i^{-1}(i<a)$的情况下就可以求出$a^{-1}$的值了。

$(\textbf{!})$但是，有一点需要注意：由于 C++ 取模运算的特殊性，被负数取模得到的值还是负数，这是我们绝对不想看到的，所以我们在具体代码实现时，需要将 $-\lfloor\dfrac{p}{a}\rfloor$ 改写为 $\left(p-\lfloor\dfrac{p}{a}\rfloor\right)$ 来实现等价而不会出现负数的操作。

实现

以下是线性递推迭代求解逆元方法的伪代码

\[\begin{array}{ll} & \textbf{Linear Modular Multiplicative Inverse Solving Algorithm }\operatorname{getInverses}(\textbf{n},\textbf{p}):\\ 1 & \textbf{Parameters. } n,p\in\mathbb{N}^+,p\text{ is a prime}.\\ & \text{Denoting the number of factors $n$ ,the modulus $b$}\\ 2 & \textbf{Returned value. } \text{An array that holds the inverse of each a}.\\ 3 & \textbf{Method.}\\ 4 & {inv}_{\operatorname{\textbf{(new)}}1}=1\\ & \mathtt{Note:}\ {inv}_{i}=i^{-1}\texttt{,which denotes the inverse of }i.\\ 5 & \textbf{for }i_{\operatorname{\textbf{(new)}}}\textbf{ from }2\textbf{ to }n\textbf{ do}\\ 6 & \qquad {inv}_i\gets\left(p-\lfloor\dfrac{p}{i}\rfloor\right)\cdot{inv}_{(p\bmod i)}\bmod p\\ 7 & \textbf{end}\\ 8 & \textbf{return }inv \end{array} \]

复杂度

显然为

\[\operatorname{O}(n) \]

优劣

优势

在要求序列$1,2,\ldots,n$里每个数的乘法逆元时，扩欧法和快速幂法都需要$\operatorname{O}(n\log p)$的复杂度来解决，此时$\operatorname{O}(n)$的线性算法就占很大优势。另外线性递推算法在数据范围小且模数确定时还可以用于打表，贴到代码上$\operatorname{O}(1)$就行了，嘻嘻。

劣势

局限性：仅当模数为质数时，线性递推法才可用

证明：感性理解一下，由于仅当 $\gcd(a,p)=1$ 时线性同余方程
$ax\equiv1\pmod{p}$ 才有解，$a^{-1}$才存在，那么当 $p$ 不为质数时，
要使线性递推法可用，$1,2,\ldots,n$ 每个数都必须与 $p$ 互质，这怎么可能呢？

仅在求$1,2,\ldots,n$的逆元时才占优势，偏要将递推式转为递归求解单个数逆元已知的复杂度上界仅为$\operatorname{O(\sqrt[3]{n})}$，更优的算法有扩欧法和快速幂法。

4.线性阶乘法

同样是求$1,2,\dots,n$这$n$个数中每个数 $a$ 在模 $p$ 意义下的逆元 $a^{-1}$，有没有一种更易于理解的方法呢？答案是肯定的。我们只需要利用逆元与原数相乘抵消成单位元的性质，即可利用阶乘求解。

过程

\[\begin{aligned} \text{显然}&\space{i!}^{-1}={(i+1)!}^{-1}\times(i+1),&(1)\\ &\space i^{-1}=\frac{(i-1)!}{i!}=(i-1)!\cdot {i!}^{-1}&(2) \end{aligned}\]

所以对于$1,2,\dots,n$，我们先处理出$1$至$n$的阶乘(模 $p$ 意义下)，然后只需要跑一遍扩展欧几里得或快速幂($p$为质数) 求出 $n!^{-1}$，然后依据$(1)$逆推就能依次求出$(n-1)!^{-1},(n-2)!^{-1},\ldots,2!^{-1},1!^{-1}$的值，同时在迭代求出$i!^{-1}$后，由于$i!,(i-1)!$已经被预处理出来了，即可用$(2)$求出$i^{-1}$.

实现

以下是线性阶乘法求逆元的伪代码

\[\begin{array}{ll} & \textbf{Factorial Modular Multiplicative Inverse Solving Algorithm }\operatorname{getInverses}(\textbf{n},\textbf{p}):\\ 1 & \textbf{Parameters. } n,p\in\mathbb{N}^+,p\text{ is a prime}.\\ & \text{Denoting the number of factors $n$ and the modulus $p$}\\ 2 & \textbf{Returned value. } \text{An array that holds the inverse of each }a\in\mathbb{N^+}\cap[1,n].\\ 3 & \textbf{Method.}\\ 4 & {fac}_{\operatorname{(new)}0}\gets 1\\ 5 & {fac}_{1}\gets 1\\ & \mathtt{Note:}\ {fac}_{i}=i!\texttt{,which denotes the factorial of }i.\\ 6 & \textbf{for }i_{\operatorname{\textbf{(new)}}}\textbf{ from }2\textbf{ to }n\textbf{ do}\\ 8 & \qquad fac_i\gets fac_{i-1}\times i\bmod p\\ 9 & \textbf{end}\\ 9 & G_{\operatorname{(new)}}\gets\operatorname{exgcd}(fac_{n},p,x_{\operatorname{(new)}},y_{\operatorname{(new)}})\\ 10 & {invfac}_{\operatorname{(new)}n}\gets(x\bmod p+p)\bmod p\\ {(\mathbf{i})} &\overline{\texttt{It's equivalent to the code below.}}\\ \mathit{10} & \underline{invfac_{\operatorname{(new)}n}\gets fac_n^{p-2}\bmod p\hspace{1.3cm}}\\ & \mathtt{Note:}\ {invfac}_{i}=i!^{-1}\texttt{,which denotes the inverse of the factorial of }i.\\ 11 & inv_{\operatorname{(new)}n}\gets invfac_{n}\times fac_{n-1}\bmod p\\ & \mathtt{Note:}\ {inv}_{i}=i^{-1}\texttt{,which denotes the inverse of }i.\\ 12 & \textbf{for } i_{\operatorname{(new)}}\textbf{ from }n-1\textbf{ to } 1\textbf{ do}\\ 13 & \qquad invfac_i\gets {invfac}_{i+1}(i+1)\bmod p\\ 14 & \qquad inv_i\gets {invfac}_{i}\times {fac}_{i-1}\bmod p\\ 15 & \textbf{end}\\ 16 & \textbf{return }inv \end{array} \]

复杂度

求 $n!^{-1}$ 的复杂度是$\operatorname{O}(\log p)$,求 $n!$ 与迭代逆推的复杂度均为$\operatorname{O}(n)$，所以总复杂度是

\[\operatorname{O}(n+\log p) \]

优劣

同线性迭代法.

5.线性前缀积-求任意n个数逆元

首先我们注意到，使用线性阶乘法时，由于是从 $n$ 开始逆推，并不依赖从 $1$ 开始到 $n$ 的条件。其次，我们使用阶乘只是为了利用逆元与原数相消的性质，完全可以把阶乘 $i!$ 看成是$1,2,\ldots,i$的前缀积，那么我们就可以用前缀积的方式，将阶乘法推广，来求任意 $n$ 个数 $a_1,a_2,\ldots,a_n$ 各自的逆元.

过程

\[\begin{aligned} \text{显然}&\space{\left({\prod_{k=1}^i{a_k}}\right)}^{-1}={{\left({\prod_{k=1}^{i+1}a_k}\right)}^{-1}}\times a_{i+1},&(1)\\ &\space a_i^{-1}=\frac{\prod_{k=1}^{i-1}a_k}{\prod_{k=1}^ia_k}=\left(\prod_{k=1}^{i-1}a_k\right)\left({\prod_{k=1}^{i}a_k}\right)^{-1}&(2) \end{aligned}\]

只需据$(1)(2)$逆推即可。我们把求积改为前缀积实现，即可大大优化算法。

实现

以下是线性前缀积的伪代码

\[\begin{array}{ll} & \textbf{Prefix product Modular Multiplicative Inverse Solving Algorithm }\operatorname{getInverses}(\textbf{n},\textbf{p},\mathbf{{^*}a}):\\ 1 & \textbf{Parameters. } n,p\in\mathbb{N}^+,p\text{ is a {prime}},\text{$a$ is a \textbf{pointer} to the address of the first element of \textbf{an array of $n$ factors}}.\\ & \text{Denoting the number of factors $n$ ,the modulus $p$ and the sequence $a$.}\\ 2 & \textbf{Returned value. } \text{An array that holds the inverse of each }a_i.\\ 3 & \textbf{Method.}\\ 4 & {prod}_{\operatorname{(new)}0}\gets 1\\ & \mathtt{Note:}\ prod_i={\prod_{k=1}^ia_k}\texttt{,which denotes the }i^{\operatorname{th}} \texttt{ prefix product in } a.\\ 5 & \textbf{for }i_{\operatorname{\textbf{(new)}}}\textbf{ from }1\textbf{ to }n\textbf{ do}\\ 6 & \qquad prod_i\gets prod_{i-1}\times a_i\bmod p\\ 7 & \textbf{end}\\ 8 & G_{\operatorname{(new)}}\gets\operatorname{exgcd}(prod_{n},p,x_{\operatorname{(new)}},y_{\operatorname{(new)}})\\ 9 & {invprod}_{\operatorname{(new)}n}\gets(x\bmod p+p)\bmod p\\ {(\mathbf{i})} &\overline{\texttt{It's equivalent to the code below.}}\\ \mathit9 & \underline{invprod_{\operatorname{(new)}n}\gets prod_n^{p-2}\bmod p\hspace{1.3cm}}\\ & \mathtt{Note:}\ {invprod}_{i}={\left(\prod_{k=1}^ia_k\right)}^{-1}\texttt{,which denotes the inverse of the prefix product of }a_i.\\ 10 & inv_{\operatorname{(new)}n}\gets invprod_{n}\times prod_{n-1}\bmod p\\ & \mathtt{Note:}\ {inv}_{i}=a_i^{-1}\texttt{,which denotes the inverse of }a_i.\\ 11 & \textbf{for } i_{\operatorname{(new)}}\textbf{ from }n-1\textbf{ to } 1\textbf{ do}\\ 12 & \qquad invprod_i\gets {invprod}_{i+1}\cdot a_{i+1}\bmod p\\ 13 & \qquad inv_i\gets {invprod}_{i}\times {prod}_{i-1}\bmod p\\ 14 & \textbf{end}\\ 15 & \textbf{return }inv \end{array} \]