Description
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
Input
输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。
Output
输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"
Sample Input
1 2 3 4 5
Sample Output
4
拓展欧几里得的应用，解二元一次不定方程的最小正整数解
首先是拓展欧几里得
令ax0+by0=gcd(a,b)
则bx1+(a%b)y1=gcd(b,a%b)
gcd(a,b)=gcd(b,a%b)
ax0+by0=bx1+(a%b)y1
由于a%b=a-a div b * b
ax0+by0=bx1+(a-a div b * b)y1
整理一下
ax0+by0=ay1+b(x1-a div b * y1)
对应系数
x0=y1
y0=x1-a div b * y1
所以只要知道方程的一个解，就可逆带得出原解
对于迭代下去
必然会有
X (xn)+gcd(a,b)yn=gcd(a,b)
显然，xn=0,yn=1
然后就可得出原方程的一组解
再来拓展到一般的方程
对于形如
ax+by=d
设gcd(a,b)=z
则有
ax0+by0=z
联立一下
用第二个式子*d/z
就有
(a/z)(x0*d)+(b/z)*(y0*d)=d
对应一下系数
x=x0*d/z,y=y0*d/z
要求的是整数解
所以d必须可以被z整除(d mod z = 0)
否则无整数解
这样便得出了一组正整数解
最后是求最小正整数解
ax+by=d
x如果增加b/z,则ax增加ab/z,
则by应减少ab/z,则y减少a/z
所以x的最小正整数解为x mod (b/z)
=、=是能推出来不假啦……
program poj1061;
type
ass=record
x,y:int64;
end;
var
i,j,k:longint;
a,b,d,x,y,m,n,l,answer,temp:int64;
ans:ass;
function min (a,b:int64):int64;
begin
if a<b then exit(a)
else exit(b);
end;
function gcd (a,b:int64):int64;
begin
if a mod b = 0 then exit(b)
else exit(gcd(b,a mod b));
end;
function extgcd (a,b:int64):ass;
var
temp:ass;
begin
if b=0 then
begin
temp.x:=1;
temp.y:=0;
exit(temp);
end;
temp:=extgcd(b,a mod b);
extgcd.x:=temp.y;
extgcd.y:=temp.x-a div b * temp.y;
end;
begin
read(x,y,m,n,l);
a:=m-n;
b:=y-x;
ans:=extgcd(a,l);
d:=gcd(a,l);
if b mod d<>0 then
begin
writeln('Impossible');
exit;
end;
answer:=ans.x*(b div d) mod (l div d);
if answer<0 then answer:=answer+abs(answer) div abs(l div d);
if answer<0 then answer:=answer+abs(l div d);
writeln(answer);
end.