「NOIP2012」同余方程 - 拓展欧几里得定理

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

求关于 \(x\) 的同余方程 \(ax \equiv 1 \pmod {b}\) 的最小正整数解。

解题思路

很简单的拓展欧几里得板子题，我们可以由同余方程得出下列等式

\[ ax + by = \gcd(a, b) \quad a, b \in \mathbb{Z} \]

利用拓展欧几里得定理求出 \(x\) 即可。对于本题 \(\gcd(a, b) \neq 1\) 的情况，只需在等式左右除以一个 \(\gcd(a, b)\)，最后结果乘上 \(\gcd(a, b)\) 即可。

代码演示

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
#include <cstdio>
#include <iostream>

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

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
int main() {
    int a, b;
    std::cin >> a >> b;

    int x, y;
    exgcd(a / gcd(a, b), b / gcd(a, b), x, y);

    std::cout << (x % b + b) % b * gcd(a, b) << std::endl;

    return 0;
}