辣鸡出题人来一发题解：

这题实际上是求逆元

原式的实质是：

\( ax + by = 1 \)

这里的 \(y\) 是辅助变量。

然后这就是标准的 exgcd 了， exgcd 的求法不再赘述，自行了解

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