1#include <iostream>
2using namespace std;
3typedef long long ll;
4
5// 返回 gcd(a, b)，同时通过引用返回 x, y
6// 使得 ax + by = gcd(a, b)
7ll exgcd(ll a, ll b, ll &x, ll &y) {
8    if (b == 0) {
9        x = 1;
10        y = 0;
11        return a;
12    }
13    ll d = exgcd(b, a % b, y, x);
14    // 注意这里参数顺序：递归时交换了 x, y 的位置
15    // 递归返回后 x 对应 y₁，y 对应 x₁
16    y -= (a / b) * x;
17    return d;
18}
19
20int main() {
21    ll a, b;
22    cin >> a >> b;
23    ll x, y;
24    ll d = exgcd(a, b, x, y);
25    cout << "gcd(" << a << ", " << b << ") = " << d << endl;
26    cout << a << " * " << x << " + " << b << " * " << y
27         << " = " << a * x + b * y << endl;
28    return 0;
29}

1#include <iostream>
2using namespace std;
3typedef long long ll;
4
5ll exgcd_iter(ll a, ll b, ll &x, ll &y) {
6    ll x0 = 1, y0 = 0; // a 的系数
7    ll x1 = 0, y1 = 1; // b 的系数
8    while (b != 0) {
9        ll q = a / b;
10        // 更新 a, b
11        ll temp = b;
12        b = a % b;
13        a = temp;
14        // 更新系数
15        temp = x1;
16        x1 = x0 - q * x1;
17        x0 = temp;
18
19        temp = y1;
20        y1 = y0 - q * y1;
21        y0 = temp;
22    }
23    x = x0;
24    y = y0;
25    return a;
26}
27
28int main() {
29    ll a, b;
30    cin >> a >> b;
31    ll x, y;
32    ll d = exgcd_iter(a, b, x, y);
33    cout << "gcd = " << d << endl;
34    cout << a << " * " << x << " + " << b << " * " << y
35         << " = " << d << endl;
36    return 0;
37}

1#include <iostream>
2using namespace std;
3typedef long long ll;
4
5ll exgcd(ll a, ll b, ll &x, ll &y) {
6    if (b == 0) { x = 1; y = 0; return a; }
7    ll d = exgcd(b, a % b, y, x);
8    y -= (a / b) * x;
9    return d;
10}
11
12// 求 a 模 m 的逆元
13// 即求 x 使得 ax ≡ 1 (mod m)
14// 条件：gcd(a, m) = 1
15ll mod_inverse(ll a, ll m) {
16    ll x, y;
17    ll d = exgcd(a, m, x, y);
18    if (d != 1) return -1; // 逆元不存在
19    return (x % m + m) % m; // 保证返回正数
20}
21
22int main() {
23    ll a, m;
24    cin >> a >> m;
25    ll inv = mod_inverse(a, m);
26    if (inv == -1) {
27        cout << "逆元不存在（gcd != 1）" << endl;
28    } else {
29        cout << a << " 模 " << m << " 的逆元为 " << inv << endl;
30        cout << "验证: " << a << " * " << inv << " mod " << m
31             << " = " << (a * inv) % m << endl;
32    }
33    return 0;
34}

1#include <iostream>
2using namespace std;
3typedef long long ll;
4
5ll exgcd(ll a, ll b, ll &x, ll &y) {
6    if (b == 0) { x = 1; y = 0; return a; }
7    ll d = exgcd(b, a % b, y, x);
8    y -= (a / b) * x;
9    return d;
10}
11
12// 解 ax ≡ c (mod m)
13// 等价于解 ax + my = c
14void solve_congruence(ll a, ll c, ll m) {
15    ll x, y;
16    ll d = exgcd(a, m, x, y);
17
18    if (c % d != 0) {
19        cout << "无解" << endl;
20        return;
21    }
22
23    // 一个特解
24    ll x0 = (ll)(((__int128)x * (c / d)) % (m / d));
25    x0 = (x0 % (m / d) + m / d) % (m / d);
26
27    cout << "共有 " << d << " 个模 " << m << " 下不同的解" << endl;
28    cout << "最小非负解: " << x0 << endl;
29    cout << "所有解 (mod " << m << "):" << endl;
30    for (ll i = 0; i < d; i++) {
31        cout << "  x = " << (x0 + i * (m / d)) % m << endl;
32    }
33}
34
35int main() {
36    ll a, c, m;
37    cin >> a >> c >> m;
38    solve_congruence(a, c, m);
39    return 0;
40}