• 做项目（多个C++、Java、Go、测开、前端项目）
• 刷算法（两个月高强度学算法）
• 背八股（40天挑战高频面试题）

同余方程

题目链接：https://kamacoder.com/problempage.php?pid=1236

我们需要求出满足以下条件的最小正整数 x：ax≡1 (mod b)

这意味着我们需要找到 x 使得 ax 除以 b 的余数是 1。这个问题实际上是一个典型的 模反元素 问题。

解题思路：

• 为了求出最小的 x，我们可以使用 扩展欧几里得算法 来求出 a 对模 b 的逆元。
• 这个算法能够求解 ax + by = gcd(a, b) 的一组整数解 (x, y)，而在 gcd(a, b) = 1 的情况下，x 即为所求的模逆元。
• 扩展欧几里得算法：扩展欧几里得算法可以通过递归或者迭代的方式实现。

下面给出C++代码实现：

#include <iostream>
using namespace std;

// 扩展欧几里得：计算 ax + by = gcd(a, b) 的解
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long gcd = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd;
}

int main() {
    long long a, b;
    cin >> a >> b;

    long long x, y;
    long long gcd = extended_gcd(a, b, x, y);

    // 由于我们只需要模 b 的正整数解，所以我们要保证 x 是正数
    x = (x % b + b) % b;

    cout << x << endl;

    return 0;
}