逆元-学习笔记

CJ_Fu · 2022-07-22 16:25:09 · 个人记录

同余逆元

定义

根据常识，a\bmod b=a-\lfloor\frac{a}{b}\rfloor\cdot b。

原式即 bx'+(a-\lfloor\frac{a}{b}\rfloor\cdot b)y'=c

展开整理，得到 ay' + b(x'-\lfloor\frac{a}{b}\rfloor\cdot y')=c

所以 x=y',y=(x'-\lfloor\frac{a}{b}\rfloor\cdot y') 是这一层一组正确的解（解其实有无数个，我们只需要求一个就可以了）

这样在辗转相除的递归中，知道下一层的解就可以得到上一层的解，最终就可以得到原问题的解。而递归的边界就是当前层的 a=1,b=0，所以当前层 x=c,y=0。

得到原问题的解 x,y 后，x'=x+kb,y'=y-ka 也是一组合法解（k 为任意整数）。

至此我们可以求出来任意满足 ax\equiv c\pmod b 的任意一组解。

求逆元的四种方法

接下来假设要求 \bmod \text{ }p 意义下 a 的逆元，即求 b 满足 a\cdot b\equiv 1\pmod p

根据上述内容，可以知道只有 a,p 互质的时候 a 有逆元。

1. 同余方程求法
   我们刚刚已经知道求解 ax\equiv b\pmod p。令 b=1 求解即可。
   求解限制：a 存在逆元。算法复杂度 O(\log_2 p)。
   扩展欧几里得法：

   void exgcd(int a, int b, int& x, int& y) {
   if (b == 0) {
       x = 1, y = 0;
       return;
   }
   exgcd(b, a % b, y, x);
   y -= a / b * x;
   }

2. 欧拉定理 + 快速幂
   定义欧拉函数 \varphi(x) 表示在 1\sim x 这些数中，有多少数和 x 互质。比如 \varphi(4)=2,\varphi(5)=4。不难发现如果数 p 是质数，那么 \varphi(p)=p-1。
   定理为 a^{\varphi(p)}\equiv 1\pmod p，所以 a 的逆元 b 为 a^{\varphi(p)-1}\bmod p。
   证明

   我们把所有小于 p 且与 p 互质的数拿出来，设为集合 r。|r|=\varphi(p)

   我们把集合 r 中的数全部乘 a 模 p，设为集合 s。

   那么 $s$ 中的数只可能是所有小于 $p$ 且与 $p$ 互质的数，所以 $s=r$。 也就是说 $\prod\limits_{i\in r}i=\prod\limits_{i\in s}i\pmod p$，即 $\prod\limits_{i\in r}i=\prod\limits_{i\in r}(i\cdot a)\pmod p$。 化简得到 $a^{|r|}\equiv 1\pmod p$ 即 $a^{\varphi(p)}\equiv 1\pmod p$。

   求解限制：a 存在逆元。算法复杂度 O(\log_2p)。

   费马小定理
   若 p\in \operatorname{Prime} ,\gcd(a,p)=1,则 a^{p-1}\equiv 1\ (\bmod\ p)
   证明
   设一个质数为 p ，我们取一个不为 p 倍数的数 a 。
   构造一个序列： A=\{1,2,3 \ldots, p-1\} ，这个序列有着这样一个性质：

   \prod_{i=1}^{n} A_{i} \equiv \prod_{i=1}^{n}\left(A_{i} \times a\right) \quad(\bmod\ p)

   证明:

   \because\left(A_{i}, p\right)=1,\left(A_{i} \times a, p\right)=1

   又因为每一个 A_{i} \times a(\bmod\ p) 都是独一无二的，且 A_{i} \times a(\bmod\ p)<p
   得证 (每一个 A_{i} \times a 都对应了一个 A_{i})
   设 f=(p-1) ! , 则 f \equiv a \times A_{1} \times a \times A_{2} \times a \times A_{3} \cdots \times A_{p-1}(\bmod\ p)

   a^{p-1} \times f & \equiv f \quad(\bmod\ p) \\ a^{p-1} & \equiv 1 \quad(\bmod\ p) \end{array}

   证毕。
   也可用归纳法证明:
   显然 1^{p} \equiv 1(\bmod\ p) ，假设 a^{p} \equiv a(\bmod\ p) 成立，那么通过二项式定理有

   p \\ 1 \end{array}\right) a^{p-1}+\left(\begin{array}{l} p \\ 2 \end{array}\right) a^{p-2}+\cdots+\left(\begin{array}{c} p \\ p-1 \end{array}\right) a+1

   因为 \left(\begin{array}{l}p \\ k\end{array}\right)=\frac{p(p-1) \cdots(p-k+1)}{k !} 对于 1 \leq k \leq p-1 成立，在模 p 意义下 \left(\begin{array}{l}p \\ 1\end{array}\right) \equiv\left(\begin{array}{l}p \\ 2\end{array}\right) \equiv \cdots \equiv\left(\begin{array}{c}p \\ p-1\end{array}\right) \equiv 0(\bmod\ p) ，那么 (a+1)^{p} \equiv a^{p}+1(\bmod\ p) ，将 a^{p} \equiv a(\bmod\ p) 带入得 (a+1)^{p} \equiv a+1(\bmod\ p) 得证。

   inline int qpow(long long a, int b) {//快速幂
   int ans = 1;
   a = (a % p + p) % p;
   for (; b; b >>= 1) {
       if (b & 1) ans = (a * ans) % p;
       a = (a * a) % p;
   }
   return ans;
   }

3. 递推求逆元
   这是一种递推，首先 1^{-1}=1，然后根据 1\sim k-1 的逆元求 k 的逆元。
   设 p=xk+y，其中 x=\lfloor\frac{p}{k}\rfloor,y=p\bmod k。
   所以 xk+y\equiv 0\pmod p，即 xk\equiv -y\pmod p。
   两边乘 -k^{-1}\cdot y^{-1}，得到 -x\cdot y^{-1}\equiv k^{-1}\pmod p
   因为 y=p\bmod k，按照递推，y 的逆元已经求过了，所以可以通过这个等式求 k 的逆元。
   求解限制：需要用到的逆元形如 1\sim N，且 N 不大。算法复杂度递推求的过程 O(N)，使用某个数的逆元是 O(1)。
   递推式：i^{-1}\equiv \begin{cases} \text{ if }i=1 & 1, \\ \text{ otherwise } & -\left \lfloor \frac pi(p\bmod\ i)^{-1} \right \rfloor \end{cases}

   inv[1] = 1;
   for (int i = 2; i <= n; ++i) {
   inv[i] = (long long)(p - p / i) * inv[p % i] % p;
   }

4. 线性求逆元
   题目给出 N 个数 a_1\sim a_n，要你分别求这 N 个数的逆元。
   可以先求出 \prod\limits_i a_i 的逆元，即 \prod\limits_ia_i^{-1} 设为 \operatorname{inv}。
   那么 a_k^{-1}=\operatorname{inv}\cdot \prod\limits_{i<k}a_i\cdot \prod\limits_{i>k}a_i。维护前缀积后缀积即可。
   求解限制：需要一开始就知道要求逆元的数有哪些。算法复杂度线性求的过程是 O(N+\log_2 p)，使用某个数的逆元是 O(1)。

   s[0] = 1;
   for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
   sv[n] = qpow(s[n], p - 2);
   for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
   for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;