题目：

大水题。

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