逆元.txt

来自「这是一个关于求乘法逆元的算发。算法精湛。值得下载！」· 文本 代码 · 共 50 行

int gcd(int a,int b,int &ar,int &br) 
{  
int    x1,x2,x3;  
int    y1,y2,y3;  
int    t1,t2,t3;
  if(0==a)
  {//有一个数为0，就不存在乘法逆元
   ar=0;
   br=0 ;
   return b;
  }
  if(0==b)
  {
   ar=0;
   br=0;
   return  a;
  }
  x1=1;
  x2=0;
  x3=a;
  y1=0;
  y2=1;
  y3=b;
  int k;
  for(t3=x3%y3;t3!=0;t3=x3%y3)
  {
   k=x3/y3;
   t2=x2-k*y2;
   t1=x1-k*y1;
   x1=y1;
   x1=y2;
   x3=y3;
   y1=t1;
   y2=t2;
   y3=t3;
  }
  if(y3==1)
  {   //有乘法逆元
   ar=y2;
   br=x1;
   return 1;
  }
  else
  {
      //公约数不为1，无乘法逆元
    ar=0;
    br=0;
    return y3;
  } 
}