#include<iostream>
using namespace std;

int Gcd(int a,int b)//求最大公约数
{
	if(b==0)
		return a;
	return Gcd(b,a%b);
}


int p,q;
void extend_Eulid(int a,int b)//扩展欧几里德算法
{
	if(b==0)
		{p=1; q=0;}
	else
	{
	extend_Eulid(b,a%b);
	int temp=p;
	p=q; q=temp-a/b*q;
	}
}


int main()
{
	int l,d1,d2,x,y,m,n,g;
	cin>>x>>y>>m>>n>>l;
	if(m==n)
		cout<<"Impossible"<<endl;
	else                     //x+m*q=y+n*q+l*p   题目数学模型
	{                        //可化为：p*l+(n-m)*q=x-y    
		if(m>n)              //与对应p * a+q * b = Gcd(a, b)
		{d2=m-n;d1=y-x;}
		else
		{d2=n-m;d1=x-y;}

		if(abs(d1)%Gcd(l,d2)!=0)
			cout<<"Impossible"<<endl;
		else
		{
			extend_Eulid(l,d2);
			g=Gcd(l,d2);
			int t=1;
			do
			{
				y=x;                    //y废物利用
				x=(q-l/g*t)*(d1/g);    //x废物利用
				t--;
			}while(x>0);   //x为第一负数，所以y为最小正整数
			cout<<y<<endl;
		}
	}

	return 0;
}
我测试了一些数据错误的如下：
/*
3 5 7 8 6
10 正确为4
12 33 55 77 9
42  正确为6
22 33 11 55 7
33 为5
*/
测试正确的数据如下：
1 3 5 7 9
8
2 4 6 8 10
4
3 6 9 12 15
4
1 2 1 1 8
Impossible
1 2 3 1 4
Impossible
1 2 3 5 4
Impossible
1 2 5 7 8
Impossible
2 3 5 7 8
Impossible
9 8 7 6 4
3
33 44 66 77 99
8

大家帮帮忙呀，查了一个晚上没查出来！心情极度……

• Re:谁能帮我看看代码（有注释）还有测试数据，谢谢啦 (1408) wuziyi2010 2010-06-13 15:18:53
  • Re:谁能帮我看看代码（有注释）还有测试数据，谢谢啦 (22) wuziyi2010 2010-06-13 15:19:37