首页 > 代码库 > POJ 1061青蛙的约会（扩展欧几里德）
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\n");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\n");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\n",ans); } return 0;}