乘法逆元

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}
void kzgcd(LL a,LL b,LL& d,LL& x,LL& y)
{
    if (!b)
    {
        d=a;x=1;y=0;
    }
    else
    {
        kzgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
LL inv(LL a, LL n)
{
    LL d,x,y;
    kzgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}
int main()
{
    long long aa,nn;
    cin>>aa>>nn;
    long long ans=inv(aa,nn);
    cout<<ans;
}