逆元的几种求法

深碍√TFBOYSˉ_ 2022-06-02 11:26 307阅读 0赞

乘法逆元的定义貌似是基于群给出的，比较简单地理解，可以说是倒数的概念的推广。  
记 a 关于模 p 的逆元为  a − 1 a^\{-1\} a−1 ,则  a − 1 a^\{-1\} a−1 满足  a a − 1 ≡ 1 ( m o d    p ) aa^\{-1\}≡ 1 (\\mod p) aa−1≡1(modp)

加减乘与模运算的顺序交换不会影响结果，但是除法不行。有的题目要求结果mod一个大质数，如果原本的结果中有除法，比如除以a,那就可以乘以a的逆元替代。

在mod p的运算中，a存在乘法逆元当且仅当a与p互质。一般题目给的p是一个大质数，所以只要a不是p的倍数，就以求乘法逆元。

目前了解到的求法有三种：

##### 1.扩展欧几里得。 a a − 1 ≡ 1 ( m o d    p ) aa^\{-1\}≡ 1(\\mod p) aa−1≡1(modp)，可以转换为 a a − 1 + p y = 1 aa^\{-1\} + py = 1 aa−1\+py=1，即是扩展欧几里得所能解的ax + by = gcd(a, b)。最常用的解法。(p可以不是质数,但a、p必须互质) #####

int x, y;  
    int extgcd(int a, int b, int &x, int &y)  
    {   
        if (b == 0){   
            x = 1;  
            y = 0;  
            return a;  
        }  
        int gcd = exgcd(b, a % b, x, y);  
        int tmp = x;  
        x = y;  
        y = tmp - (a/b) * y;  
        return gcd;  
    }  
    /* 求解ax+by=gcd(a,b)，亦即ax≡1(mod b)。函数返回值是a,b的最大公约数，而x即a的逆元。 注意a, b不能写反了。 */

##### 2.由费马小定理(p必须为质数) #####

> 若  p p p 为素数，  gcd ⁡ ( a , p ) = 1 \\gcd(a, p) = 1 gcd(a,p)=1 ，则  a p − 1 ≡ 1 ( m o d p ) a^\{p - 1\} \\equiv 1 \\pmod\{p\} ap−1≡1(modp) 。

稍作变形即是  a a p − 2 ≡ 1 ( m o d    p ) aa^\{p-2\}≡ 1(\\mod p) aap−2≡1(modp)，是不是发现了， a p − 2 a^\{p-2\} ap−2即是a的逆元，这个可以用快速幂来求。

当模p不是素数的时候需要用到欧拉定理  
 a ϕ ( p ) ≡ 1 ( m o d    p ) a^\{\\phi(p)\}≡1 (\\mod p) aϕ(p)≡1(modp)  
 a ∗ a ϕ ( p ) − 1 ≡ 1 ( m o d    p ) a\*a^\{\\phi(p)-1\}≡1 (\\mod p) a∗aϕ(p)−1≡1(modp)  
 a − 1 ≡ a ϕ ( p ) − 1 ( m o d    p ) a^\{-1\}≡a^\{\\phi(p)-1\} (\\mod p) a−1≡aϕ(p)−1(modp)  
所以 a ϕ ( m ) − 1 a^\{\\phi(m)−1\} aϕ(m)−1为a的逆元  
时间复杂度 O ( n ) O(\\sqrt n) O(n)即求出单个欧拉函数的值  
(当p为素数的时候 ϕ ( p ) = p − 1 \\phi(p)=p-1 ϕ(p)=p−1,则 ϕ ( p ) − 1 = p − 2 \\phi(p)-1=p-2 ϕ(p)−1=p−2可以看出欧拉定理是费马小定理的推广)  
PS：很少会用欧拉定理求逆元

##### 3.逆元打表 #####

有时会遇到这样一种问题，在模质数P下，求1~n的逆元 n< P（这里为奇质数）。可以O(n)求出所有逆元，有一个递推式如下  
 i n v \[ i \] = ( P − P / i ) ∗ i n v \[ P % i \] % P inv\[i\]=(P-P/i)\*inv\[P\\%i\]\\%P inv\[i\]=(P−P/i)∗inv\[P%i\]%P  
它的推导过程如下，设  P = t ∗ i + k ( k < i , 1 < i < p ) P=t\*i+k(k<i,1<i<p) P=t∗i\+k(k<i,1<i<p),则  t = P / i , k = P % i t=P/i,k=P\\%i t=P/i,k=P%i ,那么  
 ⇒ t ∗ i + k ≡ 0 ( m o d P ) ⇒ − t ∗ i ≡ k ( m o d P ) \\Rightarrow t\*i+k\\equiv 0\\pmod P\\\\ \\Rightarrow -t\*i\\equiv k \\pmod P ⇒t∗i\+k≡0(modP)⇒−t∗i≡k(modP)  
对上式两边同时除  i ∗ k i\*k i∗k，进一步得到  
 − t ∗ i n v \[ k \] ≡ i n v \[ i \] ( m o d P ) -t\*inv\[k\] \\equiv inv\[i\] \\pmod P −t∗inv\[k\]≡inv\[i\](modP)  
再把和替换掉，最终得到  
 i n v \[ i \] = ( P − P / i ) ∗ i n v \[ P % i \] % P inv\[i\]=(P-P/i)\*inv\[P\\%i\]\\%P inv\[i\]=(P−P/i)∗inv\[P%i\]%P  
初始化 inv\[1\]=1，这样就可以通过递推法求出 1~n 模奇素数 P 的所有逆元了。  
另外有个结论  1 … P 1\\ldots P 1…P 模  P P P 的所有逆元值对应  1 … P 1 \\ldots P 1…P 中所有的数，比如 P=7 ，那么  1 … P 1 \\ldots P 1…P 对应的逆元是 1 , 4 , 5 , 2 , 3 , 6 1,4 ,5 ,2 ,3 ,6 1,4,5,2,3,6

typedef  long long ll;  
    const int N = 1e5 + 5;  
    int inv[N];  
       
    void inverse(int n, int p) {   
        inv[1] = 1;  
        for (int i=2; i<=n; ++i) {   
            inv[i] = (ll) (p - p / i) * inv[p%i] % p;  
        }  
    }