莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

$ax\equiv1\pmod{b}\Rightarrow 存在\ y\ 使得\ ax+by=1，运用扩展欧几里得算法求出即可$

可参考： 扩展欧几里得算法

#include<bits/stdc++.h>

using namespace std;

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

    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;

    return d;
}

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

    int x,y;
    exgcd(a,b,x,y);

    cout<<(x%b+b)%b<<endl;

    return 0;
}