学步园

int ExtendedEuclidean(int a,int b)
{//扩展欧几里得算法求逆s=a^-1mod(b)
	int a0,b0,t0,t,s0,s,q,r;
	int temp;
	a0=a;
	b0=b;
	t0=0;t=1;s0=1;s=0;
	q=a0/b0;
	r=a0-q*b0;
	while(r>0)
	{
		temp=t0-q*t;
		t0=t;
		t=temp;
		temp=s0-q*s;
		s0=s;
		s=temp;
		a0=b0;
		b0=r;        /*********** r=gcd(a,b)
					 s*a+t*b=r      *************/
		q=a0/b0;
		r=a0-q*b0;
	}
	r=b0;
	if(s<0)s=b+s;
	return s;

}