Description

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

Input

　　一行，包含两个正整数 \(a,b\)用一个空格隔开。

Output

　　一个正整数 \(x_0\)即最小正整数解。输入数据保证一定有解。

Solution

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long a,b,x,y;
void exgcd(long long a,long long b,long long &x,long long &y)
{
    if (b==0)
    {
        x=1;y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    long long z=x;
    x=y,y=z-(a/b)*y;
}
int main()
{
    scanf("%lld%lld",&a,&b);
    exgcd(a,b,x,y);
    printf("%lld\n",(x%b+b)%b);
    return 0;
}

【模板】扩展欧几里得算法（洛谷P1082）

原文：https://www.cnblogs.com/Code-Geass/p/9929059.html