除法取模与逆元/费马小定理_数论是什么时候学的

背景

对于取余运算，有以下一些性质，加减乘都符合分配律
$$\begin{gathered} (a+b)\%p=(a\%p+b\%p)\%p \\ (a\cdot b)\%p=(a\%p\cdot b\%p)\%p \\ (a-b)\%p=(a\%p-b\%p)\%p \end{gathered}$$
但唯独除法不符合分配律
$$\frac{a}{b}\%p\ne \frac{a\%p}{b\%p}\%p$$
我们可以用乘法分配律很容易计算$a_1\cdot a_2\cdots a_n\%p$
但当我们计算$\frac{a_1\cdot a_2\cdots a_n}{b_1\cdot b_2\cdots b_n}\%p$ 时就，常见的就有组合数 $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\frac{n!}{r!\cdot (n-r)!}$ 的取余

为了解决这个问题，我们需要依赖一个著名定理：费马小定理

费马小定理

当 $p$ 为质数，对于任意的与$p$互质的整数$a$，都有 $a^{p-1}$ 取余 $p$ 等于 $1$

$$a^{p-1}\equiv 1\mathrm{mod}p,p是质数，a\perp p$$
符号说明：
$a\equiv b\mathrm{mod}c$：表示对于整数$a$,$b$,$c$，$a$ 除以 $c$ 余 $b$
$a\perp b$：表示 $a$,$b$ 互质

解决除法的取余

根据乘法的分配律，可得 $\frac{a}{b}\%p=(a\%p\cdot \frac{1}{b}\%p)\%p$
所以我们需要计算的就是 $\frac{1}{b}\%p$
设 $\frac{1}{b}\equiv b^{\prime }\%p$，我们称 $b^{\prime }$ 为 $b$ 的逆元
既 $b\cdot b^{\prime }\equiv 1\mathrm{mod}p$
根据费马小定理 $b^{p-1}\equiv 1\mathrm{mod}p$
所以 $b^{p-1}\equiv b\cdot b^{\prime }\mathrm{mod}p$
两边去同类项 $b$ 可得 $b^{\prime }\equiv b^{p-2}\mathrm{mod}p$
所以 $\frac{1}{b}\equiv b^{p-2}\mathrm{mod}p$
而 $b^{p-2}\mathrm{mod}p$ 可以通过快速幂计算得到

代码

计算组合数$\left(\genfrac{}{}{0ex}{}{n}{r}\right)$

int mod = 998244353;
int qpow(int x, int n) { 
    // 快速幂，求 x 的 n 次方
  int res = 1;
  for (; n; n >>= 1, x = 1LL * x * x % mod) 
    if (n & 1) 
      res = 1LL * res * x % mod;
  return res;
}
int binom(int n, int r) { 
   
  int res = 1;
  for (int i = 1; i <= n; i ++) { 
   
    res = 1LL * res * i % mod;
  }
  for (int i = 1; i <= r; i ++) { 
   
    res = 1LL * res * qpow(i, mod - 2) % mod;
  }
  for (int i = 1; i <= (n - r); i ++) { 
   
    res = 1LL * res * qpow(i, mod - 2) % mod;
  }
  return res;
}

练习

今天的文章除法取模与逆元/费马小定理_数论是什么时候学的分享到此就结束了，感谢您的阅读。