signed

QiShunwang

“诚信为本、客户至上”

夜深人静写算法(三十四)- 逆元(动图讲解)

2021/6/9 8:47:48   来源:

文章目录

  • 一、前言
  • 二、逆元的概念
    • 1、单位元
    • 2、逆元
    • 3、模乘的单位元
    • 4、模乘的逆元
  • 三、逆元的求解
    • 1、扩展欧几里德定理
    • 2、费马小定理
    • 3、线性递推
  • 四、逆元的应用
    • 1、前缀积差分
    • 2、逆元和高精度
    • 3、逆元和因子和
    • 4、逆元和组合数
  • 五、逆元相关题集整理

一、前言

  逆元在之前的章节已经不止一次的提及,今天再来系统性的总结一下。并不能算是一个很高深的算法,但是在数论中却有着举足轻重的地位,通常被用在加密解密算法中。
   很多读者比较疑惑,发私信给我说,为什么最近都在写数论的内容。原因其实比较简单,因为作者某一天在刷题的时候刷到了一个算法叫 “莫比乌斯反演”,搞了好久终于搞懂了,所以想写文分享出来,让全天下对热爱数论的志同道合之士都能有幸目睹这个算法的风采,但是我草率了,这个算法需要涉及的前置知识太多了,所以我才从第三十篇开始切换到了数论赛道,预计初等数论的内容可能会持续写二十篇左右,希望大家莫要嫌弃!
在这里插入图片描述

二、逆元的概念

  • 单位元 和 逆元,我们在初中和高中的时候其实就已经接触到了,只不过到了大学才系统性的给他们更加官方的命名。接下来,我们首先来了解下什么是单位元,什么是逆元。

1、单位元

【定义1】在一个集合中,对于某种运算 ∗ * (注意:这里代表通用运算的表示符号,并不是特指乘法),如果对于任何的集合元素 a a a,和元素 e e e 运算,得到还是集合元素 a a a 本身,则称 e e e 为这个运算下的单位元。

  • 在加法运算中,任意实数 a a a,有 a + e = e + a = a a + e = e + a = a a+e=e+a=a,则 单位元 e = 0 e = 0 e=0
    在这里插入图片描述
    图二-1-1
  • 在乘法运算中,任意实数 a a a,有 a × e = e × a = a a \times e = e \times a = a a×e=e×a=a,则 单位元 e = 1 e = 1 e=1
    在这里插入图片描述
    图二-1-2

2、逆元

【定义2】在一个集合中,对于某种运算 ∗ * ,如果任意两个元素的运算结果等于单位元,则称这两个元素互为逆元。

  • 在加法运算中,任意实数 a a a 的逆元为 − a -a a
    图二-2-1
  • 在乘法运算中,任意非零实数 a a a 的逆元为 a − 1 a^{-1} a1 1 a \frac 1a a1
    图二-2-2

3、模乘的单位元

  • 接下来,我们来看下模乘的单位元。
  • 对于模 n n n 乘法,所有模 n n n a a a 同余的数都可以表示成: a ( m o d   n ) = k n + a ( k ∈ Z ) a(mod \ n) = kn+ a \\ (k \in Z) a(mod n)=kn+a(kZ),令单位元为 e ( m o d   n ) e(mod \ n) e(mod n),我们将 a ( m o d   n ) a(mod \ n) a(mod n) e ( m o d   n ) e(mod \ n) e(mod n) 进行模乘操作,得到:
  • a ( m o d   n ) × e ( m o d   n ) = ( k 1 n + a ) ( k 2 n + e ) = ( k 1 k 2 n 2 + k 1 e n + k 2 a n + a e ) = ( k 1 k 2 n + k 1 e + k 2 a ) n + a e \begin{aligned} a(mod \ n) \times e (mod \ n) &= (k_1n+a)(k_2n+e) \\ &= (k_1k_2n^2+ k_1en + k_2an+ae) \\ &=(k_1k_2n+ k_1e + k_2a)n + ae \end{aligned} a(mod n)×e(mod n)=(k1n+a)(k2n+e)=(k1k2n2+k1en+k2an+ae)=(k1k2n+k1e+k2a)n+ae
  • 根据单位元的定义,有:
  • a ( m o d   n ) × e ( m o d   n ) = a ( m o d   n ) a(mod \ n) \times e (mod \ n) = a(mod \ n) a(mod n)×e(mod n)=a(mod n)
  • 代入后得到:
  • ( k 1 k 2 n + k 1 e + k 2 a ) n + a e = k n + a (k_1k_2n+ k_1e + k_2a)n + ae = kn+ a (k1k2n+k1e+k2a)n+ae=kn+a
  • 从而得到:
  • { k = k 1 k 2 n + k 1 e + k 2 a e = 1 \begin{cases} k &= k_1k_2n+ k_1e + k_2a \\ e &= 1 \end{cases} {ke=k1k2n+k1e+k2a=1
  • 所以模乘的单位元就是 1 ( m o d   n ) 1(mod \ n) 1(mod n)

4、模乘的逆元

  • 加法 和 乘法 我们已经耳熟能详了,初中就已经接触到了。所以这里我们简单复习一下,对于加法运算中的逆元,就是相反数的概念;而对于乘法运算中的逆元,就是倒数的概念。
  • 前面说了一大堆,其实都是为今天的主角做的铺垫,主要为了引出模乘的逆元,以帮助理解之用。
  • 模乘运算中,任意整数 a ( m o d   n ) a(mod \ n) a(mod n) 的逆元表示为: a − 1 ( m o d   n ) a^{-1}(mod \ n) a1(mod n)
  • 并且根据逆元的定义,满足如下等式:
  • a a − 1 ≡ 1 ( m o d   n ) aa^{-1} \equiv 1(mod \ n) aa11(mod n)
  • 可以理解成 a a a a − 1 a^{-1} a1 n n n 的作用下发生了反应,变成了 1 1 1
    图二-4-1
  • 那么逆元怎么求呢?接下来介绍几种逆元的求解方法。

三、逆元的求解

1、扩展欧几里德定理

【例题1】给定正整数 a a a b b b,求满足等式 a x + b y = 1 ax + by = 1 ax+by=1 x x x 的最小正整数解。如果不存在返回 -1。

  • 首先,我们需要提取 a a a b b b 的最大公约数,即令 g = g c d ( a , b ) g = gcd(a, b) g=gcd(a,b),则原等式可以转化为:
  • g ( a g x + b g y ) = 1 g(\frac ag x + \frac bg y) = 1 g(gax+gby)=1
  • 两个整数相乘等于 1 1 1,则他们要么都等于 1 1 1,要么都等于 − 1 -1 1,又因为任何两个数的最大公约数不可能为负数,所以 g = 1 g = 1 g=1
  • 所以当 a a a b b b 不互素时,逆元必定不存在,直接返回 − 1 -1 1
  • 那么,我们只需要考虑 a a a b b b 互素的情况。
  • 给出以下推导式:
  • a x + b y = 1 ( 1 ) = g c d ( a , b ) ( 2 ) = g c d ( b , a   m o d   b ) ( 3 ) = b x ′ + ( a   m o d   b ) y ′ ( 4 ) = b x ′ + ( a − b ⌊ a b ⌋ ) y ′ ( 5 ) = a y ′ + b ( x ′ − ⌊ a b ⌋ y ′ ) ( 6 ) \begin{aligned} ax+by &= 1 & (1) \\ &= gcd(a,b) & (2) \\ &= gcd(b, a \ mod \ b) & (3) \\ &= bx' + (a \ mod \ b) y' & (4) \\ &= bx' + (a - b\lfloor \frac a b \rfloor)y' & (5) \\ &= ay' + b(x' - \lfloor \frac a b \rfloor y' ) & (6)\\ \end{aligned} ax+by=1=gcd(a,b)=gcd(b,a mod b)=bx+(a mod b)y=bx+(abba)y=ay+b(xbay)(1)(2)(3)(4)(5)(6)
  • (1) 题目给定的等式;
  • (2) a a a b b b 互素,则 1 = g c d ( a , b ) 1 = gcd(a,b) 1=gcd(a,b)
  • (3) 最大公约数的辗转相除法,即欧几里德定理;
  • (4) g c d ( a , b ) = a x + b y gcd(a, b) = ax + by gcd(a,b)=ax+by,将 b b b 代入 a a a ( a   m o d   b ) (a \ mod \ b) (a mod b) 代入 b b b 得到 b x ′ + ( a   m o d   b ) y ′ bx' + (a \ mod \ b) y' bx+(a mod b)y
  • (5) 根据取模的定义,有: a   m o d   b = ( a − b ⌊ a b ⌋ ) a \ mod \ b = (a - b\lfloor \frac a b \rfloor) a mod b=(abba);(其中 ⌊ x ⌋ \lfloor x \rfloor x 代表 x x x 的下整)
  • (6) 按照 a a a b b b,合并同类项;
  • 根据以上六步推导后,得出:
  • a x + b y = a y ′ + b ( x ′ − ⌊ a b ⌋ y ′ ) ax+by = ay' + b(x' - \lfloor \frac a b \rfloor y' ) ax+by=ay+b(xbay)
  • 将和 a a a 相乘的部分看成 a a a 的系数,和 b b b 相乘的部分看成 b b b 的系数,从而得到:
  • { x = y ′ y = x ′ − ⌊ a b ⌋ y ′ \begin{cases} x &= y' \\ y &= x' - \lfloor \frac a b \rfloor y' \end{cases} {xy=y=xbay
  • c++ 代码实现如下:
#define ll long long

ll ExpGcd(ll a, ll b, ll &x, ll &y) {
    ll q, temp;
    if( !b ) {
        q = a; 
        x = 1; 
        y = 0;
    }else {
        q = ExpGcd(b, a % b, x, y);
        temp = x; 
        x = y;
        y = temp - (a / b) * y;
    }
    return q;
}
  • 例如,对 27 x + 8 y = 1 27x + 8y = 1 27x+8y=1 这个方程的递归求解过程如图三-1-1所示:
    图三-1-1
  • 其中,红色的线代表递归的过程,蓝色的线代表回溯的过程;
  • 红色线做的事情就是递归计算: g c d ( a , b ) → g c d ( b , a   m o d   b ) gcd(a,b) \to gcd(b, a \ mod \ b) gcd(a,b)gcd(b,a mod b)
  • 蓝色线做的事情就是回溯计算:
  • { x = y ′ y = x ′ − ⌊ a b ⌋ y ′ \begin{cases} x &= y' \\ y &= x' - \lfloor \frac a b \rfloor y' \end{cases} {xy=y=xbay
  • 递归出口则是当 b = 0 b = 0 b=0 时,由于我们已经约定了 g c d ( a , b ) = 1 gcd(a,b)=1 gcd(a,b)=1,所以这时候 a = 1 a=1 a=1,带入原方程得到:
  • { x = 1 y = 0 \begin{cases} x &= 1 \\ y &= 0\end{cases} {xy=1=0
  • 这就是递归出口时 x x x y y y 的值。然后我们通过回溯的方式,不断计算 x x x y y y 的值。

【例题2】给定正整数 a a a n n n,求满足等式 a x ≡ 1 ( m o d   n ) ax \equiv 1(mod \ n) ax1(mod n) x x x 的最小正整数解。如果不存在,则返回 − 1 -1 1

  • 这就是一个求逆元的题。 x x x 就是 a a a 在 模 n n n 乘法上的逆元。
  • 我们将 a x ≡ 1 ( m o d   n ) ax \equiv 1(mod \ n) ax1(mod n) 换一种表达形式,如下:
  • a x = k n + 1 ( k ∈ Z ) ax = kn + 1 \\ (k \in Z) ax=kn+1(kZ)
  • 移项后得到:
  • a x − k n = 1 ax - kn = 1 axkn=1
  • 由于 k k k 为整数,无论正负,所以我们将表达式变成:
  • a x + k n = 1 ax + kn = 1 ax+kn=1
  • 这时候我们发现,只要将 k k k y y y 表示, n n n b b b 表示,就变成了如下表达式:
  • a x + b y = 1 ax + by = 1 ax+by=1
  • 转化成了 【例题1】 的问题。
  • 所以,利用扩展欧几里德定理,我们可以把逆元的求解用如下函数实现:
ll Inv(ll a, ll n) {
    ll x, y;
    ExpGcd(a, n, x, y);    // (1)
    x = (x % n + n) % n;   // (2)
    return x;
}
  • (1) 利用扩展欧几里得计算 x x x 的一个可行解;
  • (2) 将 x x x 转化成最小的模 n n n 同余的正整数;

2、费马小定理

【例题3】给定素数 p p p 和 正整数 a a a,求满足 a x ≡ 1 ( m o d   p ) ax \equiv 1 (mod \ p) ax1(mod p) 的最小正整数 x x x,如果不存在返回 − 1 -1 1

  • 【例题3】和【例题2】的区别就是:模数变成了素数。所以我们可以利用费马小定理来求逆元。
  • 首先,当 a a a p p p 的倍数时, a x ≡ 0 ( m o d   p ) ax \equiv 0 (mod \ p) ax0(mod p),所以一定不存在,直接返回 − 1 -1 1
  • 否则,根据费马小定理,我们可以知道:
  • a p − 1 ≡ 1 ( m o d   p ) a^{p-1} \equiv 1 (mod \ p) ap11(mod p)
  • 则可以得到:
  • a × a p − 2 ≡ 1 ( m o d   p ) a \times a^{p-2} \equiv 1 (mod \ p) a×ap21(mod p)
  • 对比原式,就可以得到逆元 x x x 满足如下等式:
  • x = a p − 2 ( m o d   p ) x = a^{p-2} (mod \ p) x=ap2(mod p)
  • 利用二分快速幂求解即可,c++ 代码实现如下:
#define ll long long
ll Exp(ll a,ll n, ll mod){
    ll ans = 1;
    while(n) {
        if(n & 1) 
            ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

ll Inv(ll a, ll p) {
    return Exp(a, p-2, p);
}
  • 费马小定理的相关内容以及证明可以参考文章:夜深人静写算法(三十二)- 费马小定理

3、线性递推

【例题4】给定正整数 n ( n ≤ 1 0 7 ) n(n \le 10^7) n(n107) 和素数 p p p, 求 [ 1 , n ] [1, n] [1,n] 中所有整数在模 p p p 意义下的乘法逆元。

  • p = k i + r p = ki + r p=ki+r,其中 k k k 为商, r r r 为余数,且满足 r ∈ [ 0 , i ) r \in [0, i) r[0,i)
  • 即 :
  • k i + r ≡ 0 ( m o d   p ) ki+r \equiv 0 (mod \ p) ki+r0(mod p)
  • 等式两边同时乘上 i − 1 i^{-1} i1 r − 1 r^{-1} r1,从而得到:
  • k r − 1 + i − 1 ≡ 0 ( m o d   p ) kr^{-1} + i^{-1} \equiv 0(mod \ p) kr1+i10(mod p)
  • 移项,得到:
  • i − 1 ≡ − k r − 1 ( m o d   p ) ≡ − ⌊ p i ⌋ ( p   m o d   i ) − 1 ( m o d   p ) \begin{aligned}i^{-1} &\equiv - kr^{-1}(mod \ p) \\ &\equiv - \lfloor \frac p i \rfloor (p \ mod \ i) ^ {-1} (mod \ p) \end{aligned} i1kr1(mod p)ip(p mod i)1(mod p)
  • g ( i ) = i − 1 g(i) = i^{-1} g(i)=i1,则有:
  • g ( i ) = − ⌊ p i ⌋ × g ( p   m o d   i )   m o d   p g(i) = - \lfloor \frac p i \rfloor \times g(p \ mod \ i) \ mod \ p g(i)=ip×g(p mod i) mod p
  • 这样就变成了一个递推式,可以在 O ( n ) O(n) O(n) 的时间内计算出所有的 g ( i ) ( 1 ≤ i ≤ n ) g(i) (1 \le i \le n) g(i)(1in),只要用一个数组保存下来,然后递推计算即可。
  • 最后,我们来看下逆元的应用以及如何运用逆元来进行解题。

四、逆元的应用

1、前缀积差分

【例题5】给定一个长度为 n ( n ≤ 100000 ) n (n \le 100000) n(n100000) 字符串 S S S,定义 H ( s ) = ∏ i = 1 i ≤ l e n ( s ) ( S i − 28 ) (   m o d   9973 ) H(s)=\prod_{i=1}^{i≤len(s)}(S_i − 28) (\ mod \ 9973) H(s)=i=1ilen(s)(Si28)( mod 9973) 然后 Q ( Q ≤ 1000 ) Q(Q \le 1000) Q(Q1000) 个询问 ( l i , r i ) (l_i, r_i) (li,ri),求子字符串 S i : j S_{i:j} Si:j H H H 值。

  • 首先一次遍历求出 H ( i ) ( i ≤ n ) H(i) (i \le n) H(i)(in),并且利用扩展欧几里得定理求出逆元 H − 1 ( i ) ( i ≤ n ) H^{-1}(i) (i \le n) H1(i)(in)
  • 对于任意的询问 ( l , r ) (l, r) (l,r),值为 H ( r ) H ( l − 1 )   m o d   9973 \frac {H(r)} {H(l-1)} \ mod \ 9973 H(l1)H(r) mod 9973,直接转化成: H ( r ) H − 1 ( l − 1 )   m o d   9973 H(r) H^{-1}(l-1) \ mod \ 9973 H(r)H1(l1) mod 9973,每次询问时间复杂度 O ( 1 ) O(1) O(1)

2、逆元和高精度

【例题6】对于有理数 c = a b c = \frac a b c=ba,求 c   m o d   19260817 c \ mod \ 19260817 c mod 19260817 a a a b b b 不同时是 19260817 19260817 19260817 的倍数。

  • 由于 a a a b b b 不同时是 19260817 19260817 19260817 的倍数,所以当 b b b 19260817 19260817 19260817 的倍数时,分数无法化简,就不会有逆元,输出 ‘Angry!’;否则,利用费马小定理 b 19260817 − 2   m o d   19260817 b ^ {19260817-2} \ mod \ 19260817 b192608172 mod 19260817 求解 b − 1 b^{-1} b1
  • 这里 a a a b b b 非常大,可以利用大数取余先变成小于 19260817 19260817 19260817 的数。
  • 一般涉及到高精度的,为了避免高精度除法,相比于扩展欧几里得,更加推荐采用费马小定理求逆元。

3、逆元和因子和

【例题7】令 g ( n ) g(n) g(n) n n n 的因子和, 给定两个整数 a a a b b b,求: g ( a b )   m o d   9901 g(a^b) \ mod \ 9901 g(ab) mod 9901

  • a a a 进行素因子分解如下:
  • a = p 1 e 1 p 2 e 2 . . . p k e k a = p_1^{e_1}p_2^{e_2}...p_k^{e_k} a=p1e1p2e2...pkek
  • a b = p 1 b e 1 p 2 b e 2 . . . p k b e k a^b = p_1^{be_1}p_2^{be_2}...p_k^{be_k} ab=p1be1p2be2...pkbek
  • 因子和采用乘法计数,为:
  • g ( a b ) = ∏ i = 1 k p i b e i + 1 − 1 p i − 1 g(a^b) = \prod_{i=1}^k \frac {p_i^{be_i+1} - 1} {p_i - 1} g(ab)=i=1kpi1pibei+11
  • 这里分两种情况:
  • 1) p i − 1 p_i-1 pi1 不是 9901 倍数的时候,逆元一定存在,直接对每一部分进行逆元求解。
  • 2)当 p i − 1 p_i-1 pi1 是 9901 倍数的时候,即:
  • p i − 1 = 9901 k p_i-1 = 9901k pi1=9901k
  • 我们把它代入原式,得到:
  • ( 9901 k + 1 ) b e i + 1 − 1 9901 k \frac {(9901k + 1)^{be_i+1} - 1} {9901k} 9901k(9901k+1)bei+11
  • 用组合数进行展开得到:
  • = C b e i + 1 0 ( 9901 k ) b e i + 1 + . . . + C b e i + 1 b e i ( 9901 k ) 1 + 1 − 1 9901 k = T ( 9901 ) k + C b e i + 1 b e i \begin{aligned}&= \frac { C_{be_i+1}^0 (9901k)^{be_i+1} + ... + C_{be_i+1}^{be_i} (9901k)^{1} + 1 - 1} {9901k} \\ &= T(9901)k + C_{be_i+1}^{be_i} \end{aligned} =9901kCbei+10(9901k)bei+1+...+Cbei+1bei(9901k)1+11=T(9901)k+Cbei+1bei
  • 由于 T ( 9901 ) k T(9901)k T(9901)k 9901 9901 9901 的倍数,所以这部分的贡献其实就只有是 ( b e i + 1 )   m o d   9901 (be_i + 1) \ mod \ 9901 (bei+1) mod 9901
  • 对于每个素因子都利用 1)和 2)的方法求解后相乘,再模 9901 9901 9901 就是最后的答案了。
  • 考虑特殊情况,当 a = 0 a = 0 a=0 时, b = 0 b=0 b=0 结果为 1,否则结果为 0,因为 ( 0 0 = 1 ) (0^0 = 1) (00=1)

4、逆元和组合数

【例题8】给定 n ( 1 ≤ n ≤ 10000 ) n(1 \le n \le 10000) n(1n10000) 个不同的物品,要求选择其中 m m m 个,求方案数模 1 0 9 + 7 10^9+7 109+7

  • n n n 个物品选 m m m 个的方案数就是组合数 C n m C_n^m Cnm。为了书写美观,令 p = 1 0 9 + 7 p = 10^9+7 p=109+7
  • 所以这道题要求的就是:
  • n ! ( m ) ! ( n − m ) !   m o d   p \frac {n!} {(m)!(n-m)!} \ mod \ p (m)!(nm)!n! mod p
  • 所以,利用 递推 和 扩展欧几里得定理,求出所有的 i ∈ [ 0 , 10000 ] i \in [0, 10000] i[0,10000] 范围下的 i !   m o d   p i! \ mod \ p i! mod p,和 i ! − 1   m o d   p i!^{-1} \ mod \ p i!1 mod p,那么上面的式子就能够在 O ( 1 ) O(1) O(1) 的时间求解了。

  • 关于 逆元 的内容到这里就暂时结束了,如果还有不懂的问题可以留言告诉作者。

  • 本文所有示例代码均可在以下 github 上找到:github.com/WhereIsHeroFrom/Code_Templates

五、逆元相关题集整理

题目链接难度解析
luogu P1082 同余方程★☆☆☆☆【例题1】扩展欧几里得 模板题
HDU 1576 A/B★☆☆☆☆扩展欧几里得 模板题
HDU 3049 Data Processing★☆☆☆☆二分快速幂 + 逆元
HDU 1211 RSA★☆☆☆☆RSA 解密
HDU 5685 Problem A★☆☆☆☆【例题5】前缀积 + 逆元
HDU 5698 瞬间移动★★☆☆☆【例题8】组合数 + 逆元
HDU 6114 Chess★★☆☆☆组合数 + 逆元
PKU 1845 Sumdiv★★☆☆☆【例题7】因子和 + 逆元
HDU 5976 Detachment★★☆☆☆贪心 + 逆元
HDU 3240 Counting Binary Trees★★★☆☆卡特兰数 + 逆元
HDU 4828 Grids★★★☆☆卡特兰数 + 逆元
HDU 5184 Brackets★★★☆☆类卡特兰数 + 逆元
HDU 4812 D Tree★★★☆☆点分治 + 逆元
HDU 5407 CRB and Candies★★★☆☆Kummer 定理 + 逆元
luogu P3811 【模板】乘法逆元★★★☆☆【例题4】逆元 的 递推式
luogu P5431 【模板】乘法逆元2★★★☆☆后缀积 + 逆元 + 快读
luogu P2613 【模板】有理数取余★★★☆☆【例题6】费马小定理 + 大数取余 + 逆元
HDU 3074 Multiply game★★★☆☆树状数组 + 逆元
luogu P4942 小凯的数字★★★☆☆等差数列求和 + 逆元
HDU 6755 Fibonacci Sum★★★★★二次剩余 + 逆元 + 斐波那契数列通项公式 + 二分快速幂
HDU 4959 Poor Akagi★★★★★逆元+ 卢卡斯数通项公式 + 矩阵二分快速幂