求逆元基本方法

旧城等待， 2021-11-22 08:10 468阅读 0赞

**乘法逆元小结**

> 乘法逆元，一般用于求
> 
> $\\frac\{a\}\{b\} \\pmod p$
> 
> 的值（$p$ 通常为质数），是解决模意义下分数数值的必要手段。

**一、逆元定义**

> 若$a\*x\\equiv1 \\pmod b$，且$a$与$b$互质，那么我们就能定义: $x$ 为 $a$ 的逆元，记为$a^\{-1\}$，所以我们也可以称 $x$ 为 $a$ 在$\\mod b$意义下的倒数，

> 所以对于 $\\displaystyle\\frac\{a\}\{b\} \\pmod p$ ，我们就可以求出 $b$ 在 $\\bmod p$ 下的逆元，然后乘上 $a$ ，再 $\\bmod p$，就是这个分数的值了。

**二、求解逆元的方式**

**1.拓展欧几里得**

条件 $a \\bot p$（互质），但 $p$ 不是质数的时候也可以使用。

这个方法十分容易理解，而且对于单个查找效率似乎也还不错，比后面要介绍的大部分方法都要快(尤其对于 $\\bmod p$ 比较大的时候)。

这个就是利用拓欧求解 线性同余方程 $a\*x\\equiv c\\pmod\{b\}$ 的$c=1$的情况。我们就可以转化为解 $a\*x + b\*y = 1$ 这个方程。

> 引理：$ax+by=c$有解的充分条件是$gcd(a,b)|c$

所以$ax+by=gcd(a,b)①$显然有解

> 引理：$gcd(a,b)=gcd(b,a mod b)②$

将$①$代入$②$得

$ax\_1+by\_1=bx\_2+(a mod b)y\_2$  
$ax\_1+by\_1=bx\_2+(a-\[\\frac\{a\}\{b\}\]\*b)y\_2$  
$ax\_1+by\_1=bx\_2+ay-\[\\frac\{a\}\{b\}\]\*by\_2$  
$ax\_1+by\_1=ay\_2+b(x\_2-\[\\frac\{a\}\{b\}\])$

$∴x\_1=y\_2,y\_1=x\_2-\[\\frac\{a\}\{b\}\]y$

$∵a\\bot b$

$∴gcd(a,b)=1$

$∴当b=0时，a=1，此时有x=1，y的最小自然数解为0$

代码比较简单：

void Exgcd(ll a, ll b, ll &x, ll &y) {
        if (!b) x = 1, y = 0;
        else Exgcd(b, a % b, y, x), y -= a / b * x;
    }
    int main() {
        ll x, y;
        Exgcd (a, p, x, y);
        x = (x % p + p) % p;
        printf ("%d\n", x); //x是a在mod p下的逆元
    }

**2.小费尔马定理（快速幂）**

费马小定理：

> 若$p$为素数，$a$为正整数，且$a$、$p$互质。 则有$a^\{p-1\} \\equiv 1 (\\bmod p)$。

这个我们就可以发现它这个式子右边刚好为 $1$ 。

所以我们就可以放入原式，就可以得到：

$a\*x\\equiv 1 \\pmod p$

$a\*x\\equiv a^\{p-1\} \\pmod p$

$x \\equiv a^\{p-2\} \\pmod p$

所以我们可以用快速幂来算出 $a^\{p-2\} \\pmod p$的值，这个数就是它的逆元了

代码也很简单：

ll fpm(ll x, ll power, ll mod) {
        x %= mod;
        ll ans = 1;
        for (; power; power >>= 1, (x *= x) %= mod)
            if(power & 1) (ans *= x) %= mod;
        return ans;
    }
    int main() {
        ll x = fpm(a, p - 2, p); //x为a在mod p意义下的逆元
    }

**3.线性推逆元**

用于求一连串数字对于一个$\\bmod p$的逆元。[洛谷P3811][P3811]

只能用这种方法，别的算法都比这些要求一串要慢。

首先我们有一个,$1^\{-1\}\\equiv 1 \\pmod p$

然后设 $p=k\*i+r,(1<r<i<p)$ 也就是 $k$ 是 $p / i$ 的商，$r$ 是余数 。

再将这个式子放到$\\pmod p$意义下就会得到：

$k\*i+r \\equiv 0 \\pmod p$

然后乘上$i^\{-1\}$,$r^\{-1\}$就可以得到:

$k\*r^\{-1\}+i^\{-1\}\\equiv 0 \\pmod p$

$i^\{-1\}\\equiv -k\*r^\{-1\} \\pmod p$

$i^\{-1\}\\equiv -\\lfloor \\frac\{p\}\{i\} \\rfloor\*(p \\bmod i)^\{-1\} \\pmod p$

于是，我们就可以从前面推出当前的逆元了。

代码也很短：

inv[1] = 1;
    for(int i = 2; i < p; ++ i)
        inv[i] = (p - p / i) * inv[p % i] % p;

**4.阶乘逆元 $O(n)$ 求**

因为有如下一个递推关系。

$\\displaystyle inv\[i+1\]=\\frac\{1\}\{(i+1)!\}$

$\\displaystyle inv\[i+1\]\*(i+1)=\\frac\{1\}\{i!\}=inv\[i\]$

所以我们可以求出$n!$的逆元，然后逆推，就可以求出$1...n!$所有的逆元了。

递推式为

$inv\[i+1\]\*(i+1)=inv\[i\]$

所以我们可以求出 $\\displaystyle \\forall i, i!,\\frac\{1\}\{i!\}$ 的取值了。

然后这个也可以导出 $\\displaystyle \\frac\{1\}\{i\} \\pmod p$ 的取值，也就是

$\\displaystyle \\frac\{1\}\{i!\} \\times(i-1)!=\\frac\{1\}\{i\} \\pmod p$

> 如果我们需要求 $0!$ 到 $n!$ 的逆元，对于每个元素都求一遍，就显得有点慢。
> 
> 逆元可以看作是求倒数。那么不就有

> $\\displaystyle \\frac\{1\}\{(n+1)!\} \\times(n+1)=\\frac\{1\}\{n!\} \\pmod p$

int inv( int b, int p ) {
        int a, k;
        exPower( b, p, a, k );
        if( a < 0 ) a += p;
        return a;
    }
    void init( int n ) {
        Fact[ 0 ] = 1;
        for( int i = 1; i <= n; ++i ) Fact[ i ] = Fact[ i - 1 ] * i % Mod;
        INV[ n ] = inv( Fact[ n ], Mod );
        for( int i = n - 1; i >= 0; --i ) INV[ i ] = INV[ i + 1 ] * ( i + 1 ) % Mod;
        return;
    }

转载于:https://www.cnblogs.com/guoshaoyang/p/10940335.html

[P3811]: https://www.luogu.org/problem/show?pid=3811