> // alg:扩展欧几里德算法证明以及算法如下：
> //     K*e mod f = d (e,f,d为已知量) [c]
> //     设e'为 e 关于f的乘法逆元 （什么是乘法逆元？若e'满足e*e' mod f =1 则称e'为 e 关于f的乘法逆元） 则有 
> 
> //     e'*e mod f= 1  根据模运算性质有 
> 
> //     d*(e'*e) mod f=d*1=d    [d] 
> //     对比 [c] [d] 不难发现 k=d*e' mod f 
> //     所以问题转为求e的乘法逆元e'     用扩展的欧几里德算法 可以求e' .算法描述如下 
> 
> //     ExtendedEuclid(e,f) 
> //     1 (X1,X2,X3):=(1,0,f) 
> //     2 (Y1,Y2,Y3):=(0,1,e) 
> //     3 if (Y3=0) then return  e'=null//无逆元 
> //     4 if (Y3=1) then return  e'=Y2  //Y2为逆元 
> //     5 Q:=X3 div Y3 
> //     6 (T1,T2,T3):=(X1-Q*Y1,X2-Q*Y2,X3-Q*Y3) 
> //     7 (X1,X2,X3):=(Y1,Y2,Y3) 
> //     8 (Y1,Y2,Y3):=(T1,T2,T3) 
> //     9 goto 3
> 
> #include <iostream>
> #include <stdio.h>
> using namespace std;
> 
> _int64 eo(_int64 e, _int64 f)
> {
> 	_int64 x1 = 1, x2 = 0, x3 = f;
> 	_int64 y1 = 0, y2 = 1, y3 = e;
> 	_int64 t1, t2, t3;
> 	_int64 q;
> 	while(y3)
> 	{
> 		if(y3 == 1) return y2;
> 		q = x3 / y3;
> 		t1 = x1 - q * y1;
> 		t2 = x2 - q * y2;
> 		t3 = x3 - q * y3;
> 		x1 = y1;
> 		x2 = y2;
> 		x3 = y3;
> 		y1 = t1;
> 		y2 = t2;
> 		y3 = t3;
> 	}
> 	return 0;
> }
> 
> int main()
> {
> 	_int64 x, y, m, n;
> 	_int64 v, d;
> 	_int64 L;
> 	_int64 j, c;
> 	_int64 e;
> 	scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&L);
> 	if(m > n)
> 	{
> 		v = (m - n) % L;
> 		d = (x - y + L) % L;
> 	}
> 	else
> 	{
> 		v = (n - m) % L;
> 		d = (y - x + L) % L;
> 	}
> 	c = L - d;
> 	e = eo(v, L);
> 	if(e == 0)
> 	{
> 		cout<<"Impossible"<<endl;
> 		return 0;
> 	}
> 	else
> 	{
> 		j = ((e * c) % L + L) % L;
> 	}
> 	printf("%I64d\n", j);
> 	return 0;
> }

• Re:：） 好麻烦的方法啊 (12) zouyuanrenren 2006-04-13 02:24:12