AcWing 876. 快速幂求逆元

2023-10-11 13:19:04

题目传送门

一、什么是逆元？

$(a + b)\% p = (a\%p + b\%p) \%p$ （对）

$(a - b) \% p = (a\%p - b\%p) \%p$ （对）

$(a * b) \% p = (a\%p * b\%p) \%p$ （对）

$(a / b) \% p = (a\%p / b\%p) \%p$ （错）

为什么除法错的?

证明是对的难，证明错的只要举一个反例:

$(100/50)\%20 = 2 ≠ (100\%20) / (50\%20) \%20 = 0$

对于一些题目，我们必须在中间过程中进行求余，否则数字太大，电脑存不下，那如果这个算式中出现除法，会损失精度，导致答案变小。

因为除法在取模运算时没有性质 $( a/b )\% c = (a\%c /b\%c) \%c$,这个是不成立的，所以没法计算了，这时数学家提出了个逆元的概念：

比如 $3 /5 \ mod \ 7$ ,因为$5$在乘法模$7$的世界里的逆元是$3$，所以转化为 $3 * 3 \ mod\ 7$,就可转化为乘法的性质了，就方便计算了，就是答案$2$。

逆元可以代替除法，除以这个数就等于乘以这个数的逆元。

二、怎么理解逆元的含义？

想像你在一个加法的世界里，以$0$为世界的中心。有一天，你从世界的中心位置，进行了$+3$，突然，你想回到世界的中心，而你只能使用加法，所以你需要找一个数，让你加上这个数后，可以回到$0$这个世界的中心，这个数就是你在加法世界里$3$的逆元，也就是$-3$。

想像你在一个乘法取模$7$的世界里，以$1$为世界的中心，有一天，你从世界的中心位置，进行了$*3 \ mod\ 7$的操作，突然，你想回到世界的中心，而你只能使用乘法取模的，所以你需要找到一个数，让你乘上它再模$7$后，回到世界的中心，那么这个数就称为你在乘法模$7$世界的逆元。

举个栗子， $3 * 5\ mod\ 7 =1$ 那么$3$和$5$就在乘法$mod7$世界里互为逆元，就像是加法世界里的$3$和$-3$一样。

在这个乘法模$7$的世界里，逆元不是唯一的，比如 $3 * 5\ mod\ 7 =1$ 而 $3*9\ mod\ 7 =1$。我们所说的求逆元一般是指逆元当中最小的那个。

三、费马小定理

当$p$为质数时 $\large a^{p-1} \equiv 1 (mod\ p) $

⭐️小试牛刀:今天是周一，再过 $3^{2008}$ 次方天，是周几呢？

解：因为一周$7$天，其实是在求$3^{2008}\%7$。
此时$p=7$,是质数，可以用费马小定理计算同余结果:

计算$2008$与$p-1$的关系，$2008=6*334+4$

所以$3^{2008} \equiv 3^{4} (mod \quad 7) $ 就是 $81\%7=4$

今天是周一，再过四天就是周五了。

四、怎样求逆元？

当$k$为质数时，可以用费马小定理+快速幂求逆元：
$a^{p-1}≡1 (mod\quad p)$

转化一下：

$a \times a^{p-2}≡1 (mod\quad p)$

$\because$ $a^{p-2}$就是$a$的逆元。

当n不是质数时，可以用扩展欧几里得算法求逆元：

a有逆元的充要条件是a与p互质，所以gcd(a, p) = 1
假设a的逆元为x，那么有a * x ≡ 1 (mod p)
等价：ax + py = 1
exgcd(a, p, x, y)

C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

// 快速幂 (a^k)%p
LL qmi(int a, int k, int p) {
    LL res = 1;
    while (k) {
        if (k & 1) res = res * a % p;
        a = a * (LL) a % p;
        k >>= 1;
    }
    return res;
}

int main() {
    //读入优化
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    while (n--) {
        int a, p;
        cin >> a >> p;
        if (a % p == 0) puts("impossible");//互质
        else printf("%lld\n", qmi(a, p - 2, p));
    }
    return 0;
}

码农公寓