9费马小定理

费马小定理是欧拉定理的特殊情况，即当$ n $是质数（素数）的时候：

**数学公式: ** $ a^{n-1} \equiv 1 \pmod{n} $

10 乘法逆元

当我们需要计算 $ a/b\%c $，又由于 $ a,b $在运算过程中会变得非常大，不能用高精度保存的时候，典型的就是算组合数取模，这个时候可以利用乘法逆元将除法转换成乘法，并提前进行取模运算。设 $ inv \times b\equiv 1(mod\ c) $

我们称 $ inv $为$ b $对 $ c $的逆元，如果存在这样的$ inv $，就可以将除法转换成乘法，即 $ a/b\pmod{c} \equiv a \times inv \pmod{c} $ ， 接下来我们观察什么情况下会存在逆元，假设

$ a/b=k \times c+r $

两边同乘以 $ b $可得

$ a=k \times b \times c+b \times r $

两边同乘以 $ inv $ 可得：

$ a \times inv \equiv k \times c +r (mod\ c) $

到此，除法已经转换成了乘法,所以我们只需要求出$ inv $就可以了, $ inv $的求解本质上就是解一个二元一次方程: $ inv \times b+k \times c=1 $

的一个正整数解，利用扩展欧几里得求解即可。所以， $ b $和 $ c $互质的时候存在逆元，特殊的，当 $ c $是质数的时候，利用费马小定理，$ inv=b^{c-2}\%c $

求逆元代码：

int inv(int b, int c)
{
  int x, y;
  exgcd(b,c,x,y);
  x = (x % c + c ) % c;//如果x是负数，则转为整数
  return x;
}

复杂度 数学公式: $ O(\log{n}) $

10.1线性递推求逆元

可以在线性复杂度内求出数学公式: $ 1 \sim n $的逆元。 $ P $ 是质数： $ inv(i)=(P-P/i) \times inv(P\%i)\%P $

令 $ t=P/i,k= P\%i $, 则 $ t \times i + k \equiv 0 \pmod{P} $ ， $ -t \times i\equiv k \pmod{P} $ 两边同乘以$ inv(i) \times inv(k) $

$ -t \times inv(k)\equiv inv(i) \pmod{P} $ 将 $ t,k $代入即可。

线性递推求逆元代码：

void init(int n, int P){
  inv[1]=1;
  for(int i=2; i<=n; i++){
    inv[i] = (P - P /i) * inv[P % i] % P;
  }
}

复杂度 数学公式: $ O(n) $

10.2无法求逆元时如何转换除法

当$ a $和$ b $，以及 $ bm $不太大的时候，可以进行以下转换： $ \frac{a}{b}\%m=a\%(mb)/b $

证明: 左边式用带余除法展开得： $ \begin{align}\frac{a}{b}=km+x (x

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com