乘法逆元定义

若整数 b，m 互质，并且对于任意的整数 a，如果满足 b | a（b 能整除 a），则存在一个整数 x，使得 a / b ≡ a * x (mod m)，则称 x 为 b 的模 m 乘法逆元，记为 $b^{-1}$(mod m)。
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，$b^{m-2}$ 即为 b 的乘法逆元。

---

快速幂求逆元

当 p 是质数时，可以利用快速幂求逆元。
a / b ≡ a * x (mod n)
两边同乘 b 可得 a ≡ a * b * x (mod n)
即 1 ≡ b * x (mod n)
同 b * x ≡ 1 (mod n)
由费马小定理可知，当n为质数时
$b^{n-1}$ ≡ 1 (mod n)
拆一个 b 出来可得 b * $b^{n-2}$ ≡ 1 (mod n)
故当n为质数时，b的乘法逆元 x = $b^{n-2}$

#include <iostream>

using namespace std;

typedef long long LL;

int n;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

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

int main()
{
    scanf("%d", &n);
    
    while (n--) {
        int a, p;
        scanf("%d%d", &a, &p);
        
        if (a % p == 0) puts("impossible");
        else printf("%d\n", qmi(a, p - 2, p));
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

扩展欧几里得算法求逆元

当 p 不是质数时，可以用扩展欧几里得算法求逆元。
a 有逆元的充要条件是 a 与 p 互质，所以 gcd(a, p) = 1
假设 a 的逆元为 x，那么有a * x ≡ 1 (mod p) 等价：ax + py = 1
exgcd(a, p, x, y)

#include <iostream>

using namespace std;

typedef long long LL;

int n;

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}


int main()
{
    scanf("%d", &n);
    
    while (n--) {
        int a, p;
        scanf("%d%d", &a, &p);
        
        int x, y;
        int d = exgcd(a, p, x, y);
        
        if (d == 1) printf("%d\n", ((LL)x + p) % p); // 保证 x 是正数
        else puts("impossible");
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38