简介模逆运算：

假设u位模数，x位系数，r位余数，满足x*v=rmod u。但r=1时，称x为v模u的逆，即x=v-1modu；否则，即当r！=1时，称x为v模u的系数。

解法简介,模逆可以用欧几里德算法来求，不过由于除法用的太多降低了算法的速度，我们这里用steim算法来求。

以下是steim算法求模逆运算：

#include<stdio.h>              //求模逆运算的stein算法
int qiumoni(int v,int u)
{
 int x1,x3,y1,y3;
 x1=1;x3=v;
 y1=0;y3=u;
 while(x3!=1&&y3!=1) 
 {
  if(x3%2==0)
  {
   if(x1%2==0)
   {
   x1>>=1;             // x1=x1/2;
   x3>>=1;             // x3=x3/2;
   }
   else
    x1+=u;
  }
  else if(y3%2==0)
  {
   if(y1%2==0)
   {
    y1>>=1;         //y1=y1/2;
    y3>>=1;         //y3=y3/2;
   }
   else
    y1=y1+u;
  }
  else
   if(x3>y3)
  {
   x1-=y1;
   x3-=y3;
  }
  else
  {
   y1=y1-x1;
   y3=y3-x3;
  }
 }
 if(x3==1)
           return x1;
 else
        return y1;
}
int main()
{
 int v,u;
 while(scanf("%d%d",&v,&u)!=EOF)
      printf("%d\n",qiumoni(v,u));
 return 0;
}