乘法逆元

· · 个人记录

乘法逆元

定义

对于线性同余方程ax\equiv 1\pmod{b}，定义 x 为 a\ mod\ b的逆元，记作a^{-1}

逆元的一个最重要的用处是用于处理模意义下的除法，它有性质如下：

a/b\equiv a\times b^{-1} \pmod{m}

由于模意义下混合运算中的除法无法直接取模，逆元成为了处理该类除法的重要工具

扩展欧几里得算法求逆元

前置知识：扩展欧几里得算法

我们知道（不知道的点上面的链接），扩展欧几里得算法可以用于求解形如ax\equiv b\pmod{m}的线性同余方程

由逆元的定义可知，我们可以通过扩展欧几里得算法迅速求出单个乘法逆元

代码如下：

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

bool liEu(int a, int b, int c, int& x, int& y)//求解线性同余方程 
{
  int d = ex_gcd(a, b, x, y);
  if (c % d != 0) return 0;
  int k = c / d;
  x *= k;
  y *= k;
  return 1;
}

费马小定理求逆元

费马小定理： 对于素数p，若有\gcd(a,p)=1，则a^{p-1}\equiv 1\pmod{p}

证明有些复杂，这里只放链接

知道了费马小定理的内容，我们可以完成如下推导：

对于素数b，因为ax\equiv 1\pmod{b}

所以ax\equiv a^{b-1}\pmod{b}

所以x\equiv a^{b-2}\pmod{b}

因此，我们可以使用快速模幂在O(log\ b)的时间内求出单个逆元

代码如下：

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;
}

线性处理逆元

我们发现，如果每次都仅仅求单个逆元，多次查询的时间太慢了。我们是否有办法，在O(n)的线性时间内递推求出1~n的逆元呢？

首先，1^{-1}\equiv 1\pmod{m}

考虑如何由一个已知逆元推出i的逆元。令s=\lfloor \frac{p}{i}\rfloor，t=p\%i，于是有：si+t\equiv0\pmod{p}

两边同乘i^{-1}\times t^{-1}得：st^{-1}+i^{-1}\equiv 0\pmod{p}

移项得：i^{-1}\equiv -st^{-1}\pmod{p}

由t=p\%i，s=\lfloor \dfrac{p}{i}\rfloor带入得：i^{-1}\equiv -\lfloor \dfrac{p}{i}\rfloor(p\ mod\ i)^{-1}\pmod{p}

因为(p\ mod\ i)<i ,而在递推过程中我们已知：对于num<i，所有的num^{-1}

所以可以得到如下递推式 i^{-1}=\begin{cases} 1& i=1\\ -\lfloor \dfrac{p}{i}\rfloor(p\ mod\ i)^{-1}& otherwise\end{cases}

代码实现如下：

inv[1] = 1;
for (int i = 2; i <= n; ++i) 
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;//这里是负数取模

于是，我们在线性时间复杂度内，递推出了1~n的逆元