求关于x的同余方程 ax ≡ 1(mod b) 的最小正整数解。

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

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

输入数据保证一定有解。

数据范围
2≤a,b≤2∗109
输入样例：

3 10

输出样例：

7

扩展欧几里得定理 参考

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
    ll a,b;
    cin>>a>>b;
    ll x,y;
    exgcd(a,b,x,y);
    cout<<(x%b+b)%b<<endl;   //因为答案要为正数;
}