算法

exgcd

这题可以转化为给定$a,m$求一个整数$x$，满足$a\times x$和$1$同余（$\mod m$）。

显然，我们还要求一个$y$，满足$m|a\times x-1$。

然后我们就可以用exgcd求解了。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a,b,x,y;
inline ll exgcd(ll &x,ll &y,ll a,ll b){
    if(b==0){
        x=1;y=0;
        return a;
    }
    ll dl=exgcd(x,y,b,a%b);
    int z=x;
    x=y;
    y=z-y*(a/b);
    return dl;
}
int main(){
    cin>>a>>b;
    exgcd(x,y,a,b);
    cout<<((x%b+b)%b);
}