// 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:请各位帮忙看一下为什么会WA(1061青蛙约会) (0) zouyuanrenren 2006-04-04 13:19:02
  • Re:请各位帮忙看一下为什么会WA(1061青蛙约会) (0) serapherny 2006-04-08 10:59:24
    • Re:请各位帮忙看一下为什么会WA(1061青蛙约会) (0) YesXdogdog 2007-08-04 11:38:55
• ：） 好麻烦的方法啊 (1667) zymx 2006-04-08 11:00:50
  • Re:：） 好麻烦的方法啊 (12) zouyuanrenren 2006-04-13 02:24:12