\(ax+by\)

\(=gcd(a,b)\)

\(=gcd(b,a%b)\)

\(=gcd(b,a-(a/b)*b)\)

\(=bx'+(a-(a/b)*b)y'\)

\(=ay'+(x'-(a/b)y')b\)

\(x=y'\)

\(y=x'(a/b)y\)

#include
    
     #include
     
      using namespace std;pair
      
        exgcd(int x,int y){    if(x==1&&y==0)    return make_pair(x,y);    pair
       
         ans=exgcd(y,x%y);    return make_pair(ans.second,ans.first-(x/y)*ans.second);} int main(){    int a,b;    scanf("%d%d",&a,&b);    pair
        
          ans=exgcd(a,b);    printf("%d\n",(ans.first%b+b)%b);    return 0;}