求关于 $x$ 的同余方程 $ax ≡ 1 \pmod b$ 的最小正整数解。

输入格式

输入只有一行，包含两个正整数 $a,b$，用一个空格隔开。

输出格式

输出只有一行，包含一个正整数 $x$，表示最小正整数解。

输入数据保证一定有解。

数据范围

$2 \le a,b \le 2 \times 10^9$

输入样例：

3 10

输出样例：

7

#include <iostream>

using namespace std;

typedef long long LL;

LL a, b, x, y;

LL exgcd(LL a, LL b, LL &x, LL &y)  // 扩展欧几里得算法, 求x, y，使得ax + by = gcd(a, b)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

int main()
{
    cin >> a >> b;
    exgcd(a, b, x, y);
    cout << (x % b + b) % b;

    return 0;
}