POJ 1061青蛙的约会（扩展欧几里德）

对欧几里德不太熟悉，参考了网上的一些讲解又学习了一下

利用扩展欧几里德算法求线性方程的一般过程：
a*x + b*y = m

令a1 = a/gcd(a,b)
b1 = b/gcd(a,b)
m1 = m/gcd(a,b)

a*x + b*y = m两边同除以m1
a*x/m1 + b*y/m1 = m/m1 = gcd(a,b)
设x1 = x/m1 ,y1 = y/m1 则原式变为a*x1 + b*y1 = gcd(a,b)
若求出这个方程中的x1,y1，那么x = x1*m1, y = y1*m1。
由欧几里德算法gcd(a,b)=gcd(b,a%b)
所以a*x1 + b*y1= gcd(a,b) = gcd(b,a%b) = b*x2 + (a%b)*y2
令k = a/b(商) r = a%b(余数)
得到a*x1 + b*y1 = b*x2 + (a-(a/b)*b)*y2 = a*y2 + b*(x2-(a/b)*y2)
=> x1=y2，y1=x2-(a/b)*y2。

所以扩展欧几里德就是在求a和b的最大公约数的同时，
也将满足方程a*x1 + b*y1 = gcd(a,b)的一组x1和y1的值求了出来

所以x, y的一组解就是x1*m1, y1*m1，，在实际的解题中一般都会去求解x或是y的最小正数的值。以求x为例，又该如何求解呢？还是从方程入手，现在的x，y已经满足a*x+b*y=m，那么a*(x+n*b)+b*(y-n*a)=m显然也是成立的。
可以得出x+n*b(n=…，-2，-1，0，1，2，…)就是方程的所有x解的集合，由于每一个x都肯定有一个y和其对应，所以在求解x的时候可以不考虑y的取值。取k使得x+k*b>0，x的最小正数值就应该是(x+k*b)%b，但是这个值真的是最小的吗？？
如果我们将方程最有两边同时除以gcd(a,b)，则方程变为a1*x+b1*y=m1，同上面的分析可知，此时的最小值应该为(x+k*b1)%b1，
由于b1<=b，所以这个值一定会小于等于之前的值。在实际的求解过程中一般都是用while(x<0) x+=b1来使得为正的条件满足，为了更快的退出循环，可以将b1改为b(b是b1的倍数)，并将b乘以一个倍数后再加到x上。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
long long x, y, m, n, l;
long long  gcd(long long  a, long long  b){  
 	if(b == 0) return a;
 	return gcd(b, a%b);
}
void exgcd( long long  a, long long  b, long long  &x, long long  &y ){
    if( b== 0 ){
        x= 1;
        y= 0;
        return;
    }
    exgcd( b, a% b, x, y );
    long long int t = x;
    x = y;
    y= t- a/ b* y;
    return;
}
int main(){
	while(~scanf("%I64d%I64d%I64d%I64d%I64d", &x, &y, &m, &n, &l)){
		if(m == n){  // 因为x!=y 所以如果m == n则永远不可能遇到 
			printf("Impossible
");continue;
		}
		long long a = m - n;
		long long b = -l;
		long long c = y - x;
		long long p, q;
		long long d = gcd(a, b);  
		if(c%d != 0){ 					 //ax+by = m 如果m不能整除gcd(a,b)则无解 
			printf("Impossible
");continue;
		}
		long long a1, b1, c1, m1;
		c1 = c/d; a1 = a/d; b1 = b/d;   //令a1 = a/gcd(a,b),b1 = b/gcd(a,b) m1 = m/gcd(a,b)
		exgcd(a1,b1,p,q);
		long long p1 = p*c1;           //这里p表示x 
		long long ans = p1%b1;

		while(ans < 0){
			ans += b1;
		}
		printf("%I64d
",ans);
	}

    return 0;
}