乘法逆元

标签: #乘法逆元 #数论
原题目: 51Node-1256
简要描述: 乘法逆元入门题

这是一份为您准备的题目解析，采用了低心智负担、清晰直观的风格，并直接使用了您刚才掌握的 exgcd 模版。

1. 题目本质

这道题目虽然文字描述是“找出 KK 满足 K×M%N=1K \times M \% N = 1”，但它在数论中有一个非常标准的学名：

求 MM 关于模 NN 的乘法逆元。

数学翻译

题目要求的公式：

K×M%N=1K \times M \% N = 1

在数学上等价于同余方程：

M⋅K≡1(modN)M \cdot K \equiv 1 \pmod N

这不仅是一个同余方程，更可以转化为我们熟悉的不定方程（裴蜀等式）：

  • K×M=N×q+1K \times M = N \times q + 1
  • K×M−N×q=1K \times M - N \times q = 1
  • 换个未知量的名字
  • M⋅x+N⋅y=1M \cdot x + N \cdot y = 1

(其中 xx 就是我们要找的 KK，yy 是某个辅助整数)

2. 为什么能用 exgcd？

我们回顾一下扩展欧几里得算法 (exgcd) 的功能： 它可以求解 ax+by=gcd⁡(a,b)ax + by = \gcd(a, b) 的一组整数解 (x,y)(x, y)。

在本题中：

  1. 系数对应：a=M,b=Na = M, \quad b = N。
  2. 互质条件：题目明确说明 M,NM, N 互质，这意味着 gcd⁡(M,N)=1\gcd(M, N) = 1。
  3. 方程匹配：
    • 我们要求的方程：M⋅x+N⋅y=1M \cdot x + N \cdot y = 1
    • exgcd 能解的方程：M⋅x+N⋅y=gcd⁡(M,N)=1M \cdot x + N \cdot y = \gcd(M, N) = 1

结论：直接把 MM 和 NN 扔进 exgcd 函数，算出来的 xx 就是答案的雏形。

3. 唯一的坑点：正数处理

exgcd 算出来的解 xx 可能是负数。 题目要求 0<K<N0 < K < N，即要求最小正整数解。

通用处理公式：

K=(x%N+N)%NK = (x \% N + N) \% N
(这一步利用了同余的性质，把负数解“转”回正数区间)

4. 极简解题代码 (C++)

直接套用我们刚刚优化的竞赛通用模版。为了防止 10910^9 计算过程中溢出，我们使用 long long。

cpp
copy 
        
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

        /**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * date: 2025-12-05 16:08:25
 * oj: 51Node-1256
 * title: 乘法逆元
 * description: 乘法逆元入门题目
 */
#include <iostream>

using namespace std;

typedef long long ll;

ll n, m;

// 求解 ax + by = gcd(a, b)
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1; y = 0;
        return a;
    }
    // 递归反着传 (y, x)
    ll d = exgcd(b, a % b, y, x);
    
    // 回来减乘除 (y -= a/b*x)
    y -= a / b * x;
    
    return d;
}

// 求 a 在模 mod 下的逆元
ll inv(ll a, ll mod) {
    ll x, y;
    // 【安全检查】如果 a 和 mod 不互质，其实没有逆元
    // 但题目保证了互质，所以可以直接解
    exgcd(a, mod, x, y);
    
    // 【核心】防负数处理
    return (x % mod + mod) % mod;
}

int main() {
    // 关闭流同步，加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 题目输入是 M, N
    // 我们求 K * M % N = 1，即 M 关于 N 的逆元
    if (cin >> m >> n) {
        cout << inv(m, n) << endl;
    }
    
    return 0;
}

5. 总结 (Cheat Sheet)

见到 Ax%B=1Ax \% B = 1 或 Ax≡1(modB)Ax \equiv 1 \pmod B：

  1. 认出它：这是求逆元。
  2. 联想它：Ax+By=1Ax + By = 1。
  3. 解决它：用 exgcd(A, B, x, y)。
  4. 修正它：(x % B + B) % B。