[NOIP 2012 提高组] 同余方程

题意

求同余方程：

a x ≡ 1 (mod b)

的最小正整数解。

思路

先看一个最直接的小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 a, b;
    cin >> a >> b;

    // brute.cpp：小数据暴力枚举最小正整数解。
    for (i64 x = 1; x <= b; x++) {
        if ((a * x) % b == 1) {
            cout << x << '\n';
            return 0;
        }
    }

    return 0;
}

暴力做法就是从 1 开始枚举 x，直到找到：

(a * x) % b == 1

这个思路最贴题意，但 b 最大到 2e9，显然不能枚举。

关键观察是，把题目改写一下：

a x ≡ 1 (mod b)

等价于：

a x + b y = 1

这正是扩展欧几里得处理的形式。

因为当 gcd(a, b) = 1 时，扩展欧几里得能求出一组整数解：

满足：

a x + b y = 1

那就说明：

a x ≡ 1 (mod b)

于是这个 x 就是 a 在模 b 下的一个逆元。
最后把它调整到最小正整数范围：

(x % b + b) % b

这就是答案。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    i64 d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

i64 inverse(i64 a, i64 mod) {
    i64 x, y;
    i64 d = exgcd(a, mod, x, y);
    if (d != 1) {
        return -1;
    }
    return (x % mod + mod) % mod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 a, b;
    cin >> a >> b;

    cout << inverse(a, b) << '\n';
    return 0;
}

复杂度

扩展欧几里得的时间复杂度是：

$O(log b)$

空间复杂度：

$O(1)$

总结

这题本质上就是一道模逆元模板题。

一旦看到：

a x ≡ 1 (mod b)

就要想到把它改写成：

a x + b y = 1

然后直接用 exgcd 求一组解。

[NOIP 2012 提高组] 同余方程

目录

题意

思路

代码

复杂度

总结