python

4.3 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

乘法逆元小结

https://www.freesion.com/article/43361201366/

乘法逆元，一般用于求

\large \frac{a}{b} \ \ \ (mod \  \ p)

的值，(p通常为质数),是解决模意义下分数数值的必要手段。

一、逆元定义

很明显，上述式子只有一条不成立，即 (a/b) \% p，但是在有些情况下，又需要进行有模运算的除法。因为式子不成立，如果 a 过大或者 b 过大，极易导致计算过程丢失精度，造成结果误差。因此，为了杜绝这一现象，逆元出现了。

若a\times x \equiv 1 (mod \ b)，且a与b互质，那么我们就能定义：

x为a的逆元,记为a^{-1},所以我们也可以称x为a在mod \ b意义下的倒数。

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

二、求解逆元的方式

1、费马小定理+快速幂求逆元(p一定要质数)

费马小定理

若p为素数，a为正整数，且a、p互质。则有a^{p−1}≡1(mod \ p)。

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

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

\large a \times x \equiv 1 (mod \ \ p )

\large a \times x \equiv a^{p-1} (mod \ \ p )

\large x \equiv a^{p-2} (mod \ \ p )

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

代码也很简单：

typedef long long LL;
LL qmi(LL a, LL k, LL p) {
    LL res = 1;
    while (k) {
        if (k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

int main() {
    int a, p;
    cin >> a >> p;
    LL x = qmi(a, p - 2, p); // x为a在mod p意义下的逆元
    return 0;
}

2、欧拉定理求逆元(相当于费马小定理的扩展)

解法一的拓展:欧拉定理+快速幂求逆元(p不一定为质数,但a p还是要互质) 一般不用这种办法，因为它能干的，扩展欧几里得都能干！略

3、扩展欧几里得

注意：(p不用为质数但a,p要互质，不然a^{-1}无解)

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

这个就是利用拓欧求解线性同余方程 a∗x≡c(mod \ b) 的c=1的情况。我们就可以转化为解 a∗x+b∗y=1 这个方程。

求解这个方程的解。不会拓欧可以点这里~

而且这个做法还有个好处在于，当 a⊥p （互质），但 p 不是质数的时候也可以使用。

代码比较简单：

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下的逆元
}

4、递推打表

用于求一连串数字对于一个mod \ p的逆元。 P3811 【模板】乘法逆元对于一个区间的逆元，只能用这种方法，别的算法都比这个要慢。

O(n)筛1到n所有数模p的逆元：

初值\large Inv[1]=1
设\large p=ki+r,则 \large ki+r \equiv 0 (mod \ p)
两边同乘\large i^{-1}r^{-1},得\large kr^{-1}+i^{-1} \equiv 0 (mod \ p)
移项：\large i^{-1} \equiv -kr^{-1} (mod \ \ p )
\large k=\left \lfloor \frac{p}{i} \right \rfloor,所以-k \equiv p- \frac{p}{i} (mod \ \ p )
所以Inv[i]=(p-p/i)*Inv[p%i]%p