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

1. 题目本质

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

求 $M$ 关于模 $N$ 的乘法逆元。

数学翻译

题目要求的公式：

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

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

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

(其中 $x$ 就是我们要找的 $K$，$y$ 是某个辅助整数)

2. 为什么能用 exgcd？

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

在本题中：

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

结论：直接把 $M$ 和 $N$ 扔进 exgcd 函数，算出来的 $x$ 就是答案的雏形。

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

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

通用处理公式：

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

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

/**
 * Author by Rainboy blog: https://blog.roj.ac.cn 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 = 1$ 或 $Ax \equiv 1 \pmod B$：

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