【算法讲解】数论

对于取余运算，有以下一些性质，加减乘都符合分配律 ( a + b ) % p = ( a % p + b % p ) % p ( a ⋅ b ) % p = ( a % p ⋅ b % p ) % p ( a − b ) % p = ( a % p − b % p ) % p (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\\ (a+b)%p=(a%p+b%p)%p(a⋅b)%p=(a%p⋅b%p)%p(a−b)%p=(a%p−b%p)%p 但唯独除法不符合分配律 a b % p ≠ a % p b % p % p \frac{a}{b}\%p \neq \frac{a\%p}{b\%p}\%p ba​%p=b%pa%p​%p 我们可以用乘法分配律很容易计算 a 1 ⋅ a 2 ⋯ a n % p a_1\cdot a_2\cdots a_n\%p a1​⋅a2​⋯an​%p 但当我们计算 a 1 ⋅ a 2 ⋯ a n b 1 ⋅ b 2 ⋯ b n % p \frac{a_1\cdot a_2\cdots a_n}{b_1 \cdot b_2\cdots b_n}\%p b1​⋅b2​⋯bn​a1​⋅a2​⋯an​​%p 时就，常见的就有组合数 ( n r ) = n ! r ! ⋅ ( n − r ) ! \binom{n}{r} =\frac{n!}{r!\cdot (n-r)!} (rn​)=r!⋅(n−r)!n!​ 的取余

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

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

a p − 1 ≡ 1 m o d    p , p 是质数， a ⊥ p a^{p-1}\equiv1\mod p, p是质数，a \perp p ap−1≡1modp,p是质数，a⊥p 符号说明： a ≡ b m o d    c a\equiv b \mod c a≡bmodc：表示对于整数 a a a, b b b, c c c， a a a 除以 c c c 余 b b b a ⊥ b a\perp b a⊥b：表示 a a a, b b b 互质

根据乘法的分配律，可得 a b % p = ( a % p ⋅ 1 b % p ) % p \frac{a}{b}\%p=(a\%p\cdot \frac{1}{b}\%p)\%p ba​%p=(a%p⋅b1​%p)%p 所以我们需要计算的就是 1 b % p \frac{1}{b}\%p b1​%p 设 1 b ≡ b ′ % p \frac{1}{b}\equiv b'\%p b1​≡b′%p，我们称 b ′ b' b′ 为 b b b 的逆元 既 b ⋅ b ′ ≡ 1 m o d    p b\cdot b' \equiv1\mod p b⋅b′≡1modp 根据费马小定理 b p − 1 ≡ 1 m o d    p b^{p-1}\equiv1\mod p bp−1≡1modp 所以 b p − 1 ≡ b ⋅ b ′ m o d    p b^{p-1}\equiv b\cdot b'\mod p bp−1≡b⋅b′modp 两边去同类项 b b b 可得 b ′ ≡ b p − 2 m o d    p b' \equiv b^{p-2} \mod p b′≡bp−2modp 所以 1 b ≡ b p − 2 m o d    p \textcolor{Red}{\frac{1}{b}\equiv b^{p-2} \mod p} b1​≡bp−2modp 而 b p − 2 m o d    p b^{p-2} \mod p bp−2modp 可以通过快速幂计算得到

计算组合数 ( n r ) \binom{n}{r} (rn​)