欧几里德的是来求最大公约数的，扩展欧几里德，基于欧几里德实现了一种扩展，是用来在已知a, b求解一组x，y使得ax+by = Gcd(a, b) =d(解一定存在，根据数论中的相关定理，证明是用裴蜀定理)，关于欧几里德的证明请看上篇。
基本算法:基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。
证明：设a>b;
1. 显然当b=0，gcd(a, b) = a;此时x=1, y=0;这个就是递归出口；
2. ab!=0 时
设 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b)
则:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;(这个式子是递归的另外一部分，很重要的一步)
这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。
所以求代码可以如下
int exgcd(int a, int b, int &x, int &y)
{
if (b == )
{
x = ;
y = ;
return a; // a,b的最大公约数的求法(gcd)
}
int r = exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * y;
return r;//最大公约数
}
POJ 1061青蛙的约会这个题是求不定方程的解的，有题意可列方程(n-m)*s + k * L = x - y; 、
令a = n - m; b = L; c = x - y;
这个式子这时就是a * s + b * k = c;典型的不定方程
求解过程：
1. 首先计算gcd(a, b); 如果c不能整除gcd(a, b)那么就是没有解的，因为gcd(a, b)是a*s+b*k的线性组合的最小正整数, x,y∈z; 否则，方程两边同时除以gcd(a, b)得到新的方程a' * s + b' * k = c'; 这时候a', b'是互质的，所以gcd(a', b') = 1。
2. 利用上面所说的欧几里德算法求出方程a' * s + b' * k = 1的一组整数解x0,y0, 那么c' * x0, c' * y0就是方程a' * s + b' * k = c' 的一组整数解
3. 求方程组的通解，这时候就需要一些数论中的证明(a' * s + b' * k = c' 可以写成 a' * (s + t * b') + b' * (k - t * a') = c'， t为整数， 所以通解s通=s + t * b', k通= k - t * a')
通解为：s通=s + t * b', k通= k - t * a'
所以它的最小正整数解为 (t % b' + b') % b';
代码如下：
#include <cstdio>
#include <iostream> typedef long long LL; int gcd(LL a, LL b)
{
return b == ? a : gcd(b, a % b);
}
void exgcd(LL a, LL b, LL &x, LL &y)
{
if (b == )
{
x = ;
y = ;
return;
}
exgcd(b, a % b, x, y);
LL t = x;
x = y;
y = t - (a / b) * y;
}
int main()
{ LL x, y, n, m, L;
while (~scanf("%I64d %I64d %I64d %I64d %I64d", &x, &y, &m, &n, &L))
{
LL a, b, c, r, k1, k2, GCD;
a = n - m;
b = L;
c = x - y;
GCD = gcd(a, b);
if (c % GCD != )
{
puts("Impossible");
}
else
{
a /= GCD;
b /= GCD;
c /= GCD;
exgcd(a, b, k1, k2);
k1 *= c;//为其中一个解
k1 = (k1 % b + b) % b;//最小正整数解
printf("%I64d\n", k1);
}
}
return ;
}