目录

题目-同余方程

在这里插入图片描述

问题分析

因为无法判断 a , b a, b a,b是否互质, 无法使用求逆元的方式求 x x x, 只能用扩展欧几里得算法求出一组特解, 然后根据通解公式, 计算出最小正整数解

算法步骤

将式子转化为 a x + b y = 1 ax + by = 1 ax+by=1, 得到特解(x_0, y_0), 通解等于 x = x 0 + k ⋅ b d x = x_0 + k \cdot \frac{b}{d} x=x0​+k⋅db​, 最小正整数解等价于 x 0 + k ⋅ b d ≥ 0 x_0 + k \cdot \frac{b}{d} \ge 0 x0​+k⋅db​≥0, 因为 x ≠ 0 x \ne 0 x=0并且 gcd ⁡ = 1 \gcd = 1 gcd=1, 也就得到了 x 0 + k ⋅ b > 0 x_0 + k \cdot b > 0 x0​+k⋅b>0, 也就是 x 0 m o d    b x_0 \mod b x0​modb的正余数

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int a, b;

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

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

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

    cin >> a >> b;
    LL x, y;
    exgcd(a, b, x, y);

    LL ans = (x % b + b) % b;
    cout << ans << '\n';

    return 0;
}