__int64 Euclid(__int64 a,__int64 b) 
{ 
   __int64 n1=a,n2=b,x1=1,y1=0,q,r,x2=0,y2=1,t;
   if(n2==0){x=1;y=0;return n1;}
   loop:
   q=n1/n2;r=n1-q*n2;
   if(r==0){x=x2;y=y2;return n2;}
   else
   {n1=n2;n2=r;t=x2;x2=x1-q*x2;x1=t;t=y2;y2=y1-q*y2;y1=t;
   goto loop;
   } 
}

• if (E == 0 || T == 0) return 0;好像有问题,不应该是返回0吧 (0) ecjtubaowp 2007-05-20 17:36:44
  • 返回的是E的逆元，而且E和T也不可能是0吧 (0) xiaox 2007-05-20 17:55:44
    • 我写的这个是返回的gcd,gcd(a,b)=a*x+b*y,y为b模a的逆元 (0) ecjtubaowp 2007-05-20 18:05:30