乘法逆元
何为乘法逆元？
对于两个数 a , p a,p a,p若 gcd ( a , p ) = 1 \gcd(a,p)=1 gcd(a,p)=1则一定存在另一个数 b b b，使得 a b ≡ 1 ( m o d p ) ab\equiv1(\mod p) ab≡1(modp)，并称此时的 b b b为 a a a关于 1 1 1模 p p p的乘法逆元。我们记此时的 b b b为 i n v ( a ) inv(a) inv(a)或 a − 1 a^{-1} a−1。
举个例子： 5 × 3 ≡ 1 ( m o d 14 ) 5\times 3\equiv1(\mod 14) 5×3≡1(mod14)，我们称此时的 3 3 3为 5 5 5关于 1 1 1模 14 14 14的乘法逆元。
如何求乘法逆元？
方法一：费马小定理
费马小定理：当有两数 a , p a,p a,p满足 gcd ( a , p ) = 1 \gcd(a,p)=1 gcd(a,p)=1， p p p是质数时，则有 a p ≡ a ( m o d p ) a^{p}\equiv a(\mod p) ap≡a(modp)。
变一下形： a ⋅ a p − 2 ≡ 1 ( m o d p ) a\cdot a^{p-2}\equiv1(\mod p) a⋅ap−2≡1(modp)。是不是和上面的乘法逆元的定义是相似的？
所以，我们可以使用快速幂求出 a p − 2 a^{p-2} ap−2，即求出 a a a的逆元。
方法二：扩展欧几里得算法
由定义可知： a b ≡ 1 ( m o d p ) ab\equiv 1(\mod p) ab≡1(modp)，这个式子等价于已知 a , p a,p a,p求一个二元一次不定方程 a b = k p + 1 ab=kp+1 ab=kp+1，移一下项得： a b − k p = 1 ab-kp=1 ab−kp=1。这东西不是扩展欧几里得算法？
方法三：递推计算阶乘的逆元
当我们要计算一大串连续的阶乘的逆元时，采用费马小定理或扩展欧几里得算法就有可能超时，所以我们必须采用一个更快的算法。
令 f i = i ! f_i=i! fi=i!，则可得： i n v ( f i + 1 ) ≡ i n v ( f i ⋅ ( i + 1 ) ) ( m o d p ) inv(f_{i+1})\equiv inv(f_i\cdot (i+1))(\mod p) inv(fi+1)≡inv(fi⋅(i+1))(modp)
我们将 ( i + 1 ) (i+1) (i+1)乘过去，则有： i n v ( f i ) ≡ i n v ( f i + 1 ) ⋅ ( i + 1 ) ( m o d p ) inv(f_{i})\equiv inv(f_{i+1})\cdot(i+1)(\mod p) inv(fi)≡inv(fi+1)⋅(i+1)(modp)
自然我们就得出递推式。
方法四：递推计算连续的数的逆元
当我们要计算连续的数的逆元时，我们可以采用以下递推式： i n v ( i ) = ( p − ⌊ p i ⌋ ) × i n v ( p m o d i ) m o d p inv(i)=(p-\lfloor\frac{p}{i}\rfloor)\times inv(p\mod i)\mod p inv(i)=(p−⌊ip⌋)×inv(pmodi)modp
UPD@2019.10.9:补上这个式子的证明
证明：设 t = ⌊ p i ⌋ , k = p m o d i t=\lfloor\frac{p}{i}\rfloor,k=p\mod i t=⌊ip⌋,k=pmodi，那么显然有 t × i + k ≡ 0 ( m o d p ) t\times i+k\equiv 0(\mod p) t×i+k≡0(modp)
变形可得 − t × i ≡ k ( m o d p ) -t\times i\equiv k(\mod p) −t×i≡k(modp)
两边同时除以 i k ik ik得到 − t × 1 k ≡ 1 i ( m o d p ) -t\times\frac{1}{k}\equiv\frac{1}{i}(\mod p) −t×k1≡i1(modp)
即 i n v ( i ) ≡ − t × i n v ( k ) ( m o d p ) inv(i)\equiv-t\times inv(k)(\mod p) inv(i)≡−t×inv(k)(modp)
所以有 i n v ( i ) = ( p − ⌊ p i ⌋ ) × i n v ( p m o d i ) m o d p inv(i)=(p-\lfloor\frac{p}{i}\rfloor)\times inv(p\mod i)\mod p inv(i)=(p−⌊ip⌋)×inv(pmodi)modp
乘法逆元的作用？
我们由费马小定理可得： a ⋅ a p − 2 ≡ 1 ( m o d p ) a\cdot a^{p-2}\equiv 1(\mod p) a⋅ap−2≡1(modp)。
所以： a p − 2 ≡ a − 1 ≡ 1 a ( m o d p ) a^{p-2}\equiv a^{-1}\equiv\frac{1}{a}(\mod p) ap−2≡a−1≡a1(modp)
我们又知道模运算的乘法结合律： b a ≡ b ⋅ a − 1 ≡ b ⋅ a p − 2 ( m o d p ) \frac{b}{a}\equiv b\cdot a^{-1}\equiv b\cdot a^{p-2}(\mod p) ab≡b⋅a−1≡b⋅ap−2(modp)
所以我们可以知道： a a a除以一个数模 p p p，等于 a a a乘这个数的乘法逆元模 p p p。
编程实现
费马小定理：
long long PowMod(long long a,int b) {
long long ret=1; while(b) {
if(b&1)ret=ret*a%Mod; a=a*a%Mod; b>>=1; } return ret; } 程序内调用PowMod(a,Mod-2)即可。
扩展欧几里得算法：
long long extend_gcd(long long a,long long b,long long &x,long long &y) {
if(a==0&&b==0) return -1ll; if(b==0) {
x=1ll; y=0ll; return a; } long long d=extend_gcd(b,a%b,y,x); y-=a/b*x; return d; } long long mod_reverse(long long a,long long n) {
long long x,y,d=extend_gcd(a,n,x,y); if(d==1) {
if(x%n<=0)return x%n+n; else return x%n; } else return -1ll; } 递推计算阶乘的逆元：
f[0]=1; for(int i=1;i<=N;i++) f[i]=f[i-1]*i%Mod; inv[0]=1; inv[N]=PowMod(f[N],Mod-2); for(int i=N-1;i>0;i--) inv[i]=inv[i+1]*(i+1)%Mod; 递推计算连续的数的逆元：
inv[1]=1; for(int i=2;i<=N;i++) inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod; 发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/228249.html原文链接：https://javaforall.net
