青蛙问题,高手帮忙啊!(50分)

青蛙的约会

Time Limit:10S Memory Limit:10000K
Total Submit:361 Accepted:22

Description

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现
它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前
忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过
青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除
非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐
观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往
西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐
标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一
次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
Input
输入只包括一行5个整数x，y，m，n，L，其中x≠y，m、n≠0，L>0。m，n的符号表示了相应的青蛙的前进方向。
Output
输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"
Sample Input
1 2 3 4 5
Sample Output
4
要求程序尽可能的快啊!不能超过10秒!

1.我看题目还以为是NOI2000的青蛙过河呢.
2.我的算法很呆的,虽然10秒内能出结果.你最好还是等大侠们的数学方法.
//返回需要的步数,0表示永远无法碰面
function GetAnswer(x, y, m, n, L: Integer): Integer;
var
Distance: Integer;
Delta: Integer;
Step: Integer;
Flag: array [1..1000000] of Boolean;
begin
Result:=0;
FillChar(Flag, SizeOf(Flag), 0);
Distance:=y-x;
if Distance<0 then
Distance:=Distance+L;
Delta:=m-n;
while Delta<0 do
Inc(Delta, L);
Flag[Distance]:=True;
Step:=0;
while Distance<>0 do
begin
Inc(Step);
Dec(Distance, Delta);
if Distance<0 then
Distance:=L-Abs(Distance);
if Flag[Distance] then
Exit
else
Flag[Distance]:=True
end;
Result:=Step
end;

谢谢你的解答！
欢迎各路高手继续作答！

判断1000000次好像不能解决问题吧！！
大家帮帮我啊！

楼主误会程序的意思了,10000000并不是判断的次数,而是L的最大取值.
如果你给我个L的取值范围,我就不会写10000000了.
这个算法效率是不太好,但逻辑上不会有什么问题.

干脆换个写法:
//返回需要的步数,0表示永远无法碰面
function GetAnswer(x, y, m, n, L: Integer): Integer;
var
Distance: Integer;
Delta: Integer;
Step: Integer;
Flag: array of Boolean;
begin
Result:=0;
SetLength(Flag, L+1);
FillChar(Flag, SizeOf(Flag), 0);
Distance:=y-x;
if Distance<0 then
Distance:=Distance+L;
Delta:=m-n;
while Delta<0 do
Inc(Delta, L);
Flag[Distance]:=True;
Step:=0;
while Distance<>0 do
begin
Inc(Step);
Dec(Distance, Delta);
if Distance<0 then
Distance:=L-Abs(Distance);
if Flag[Distance] then
Exit
else
Flag[Distance]:=True
end;
Result:=Step
end;

呵呵，你们真有时间呀。
我不想想这个问题。
太累了。
太困了。
我去睡觉了。

function getmyresult(x,y,m,n,l:integer):string;
var flag:boolean;
I:integer;
begin
for I:=1 to L do
begin
if ((x+m*I) mod L)=((y+n*I) mod L) then
begin
flag:=true;
result:=inttostr(I);
break;
end;
end;
if not flag then
result:='impossible';
end;

to 魔鬼:
千万不能认为重复了l次没有结果就无解.

我绝对是正确的，慢慢领悟吧
不过我只考虑了两蛙同向
反向的话也不难

对对,是正确的,到也不用慢慢领悟.
但有时候确实可以很早判断出无解情况,又何必非要重复L次呢?

先做一下预处理：
//统一跳跃方向
if m<0 then m:=L+(m mod L);
if n<0 then n:=L+(n mod L);
//将步长范围限制在0..L-1
m:=m mod L;
n:=n mod L;

好了，现在前进方向和步长范围都已经统一。由于本问题的对称性，我们不妨设跳得快的
步长为m，另一只为n（如果发现统一化之后的m和n相等——那么它们显然不能碰面）。此时
情况变成快的在追慢的，为了处理的方便，我们让它们在出发的时候慢者在前，快者在后，
以形成追逐。为了达到这个前后效果，有必要进行再次预处理：
//将x,y限制在0..L-1
if x<0 then x:=L+(x mod L) else x:=x mod L;
if y<0 then y:=L+(y mod L) else y:=y mod L;
//让慢者在快者之前
if y<x then
y:=y+L;

好了，现在，可以写出数学表达式了： D=((x-y)+k*(m-n)) mod L ——求使得D为零
的最小自然数k。此式可以进一步被化为： (x-y)+k*(m-n)=N*L (N为整数，且N>=0)

容易看出，若(y-x) mod (m-n)=0，那么在它们的相对位置变化一圈之内快者就可以追上
慢者，所需步数为：
k=(y-x) div (m-n)

如果不能整除，我们可以用循环来试探求解，不过，值得讨论的是循环次数的上限。我们
可以得到计算公式： k=(N*L+(y-x))/(m-n) 通过在循环中改变N的值，一旦求得的k为整
数，任务就完成了。当然，有可能无论N取何值，k始终都不会为整数，我们的任务就是用尽
可能少的循环实现正确的判断。

因为目标k是整数，我们可以将上式进一步化为：
{ N*[L mod (m-n)] + (y-x) mod (m-n) } mod (m-n) = 0
==> (N*a + b) mod c = 0 （易知0<=a<c，0<b<c（b=0的情况已被排除），另外，
容易看出，若此时a=0，那么不可能追到）
为了知道是否有一个非负的整数N使得本等式成立，我们可以将试探范围限制在 [1,c) 即
可（此前已经将N=0的情况过滤掉了）


具体代码如下：

// 作者： creation_zy
// 时间： 2003-6-1
// 功能： 计算座标分别为x,y，步长分别为m,n的两只青蛙，在长度为L的纬线上
// 跳跃直至相遇所需的步数
// 返回： 返回值为所需步数，如果不能相遇，则返回-1
function GetJumpStep(x,y,m,n,L:integer):Integer;
var
i,a,b,c,temp:integer;
begin
Result:=-1;
//统一跳跃方向
if m<0 then m:=L+(m mod L);
if n<0 then n:=L+(n mod L);
//将步长范围限制在0..L-1
m:=m mod L;
n:=n mod L;
if m<n then //swap
begin
temp:=m;
m:=n;
n:=temp;
temp:=y;
y:=x;
x:=temp;
end;
//将x,y限制在0..L-1
if x<0 then x:=L+(x mod L) else x:=x mod L;
if y<0 then y:=L+(y mod L) else y:=y mod L;
//让慢者在快者之前
if y<x then
y:=y+L;

if x=y then //位置相同
begin
Result:=0;
exit;
end;

c:=m-n;
if c=0 then //间距不会变化，无解
exit;

b:=(y-x) mod c;
if b=0 then
begin
Result:=(y-x) div c;
exit;
end;

a:=L mod c;
if a=0 then //间距不会变化，无解
exit;

for i:=1 to c-1 do
begin
if (i*a+b) mod c=0 then
begin
Result:=(i*L+(y-x)) div c;
break;
end;
end;
end;


可能有错误，还请大家帮助检查，谢谢！

g z

本来想用孙子定理一次性计算出来的，没想到也要试探——得，还是继续优化我的循环吧...

新的算法将循环次数从原来的 c-1 次减少到了 a div PubGCD (PubGCD为a,b,c的最大公
约数) 次（因为 a=L mod c，所以a得取值范围为[0..c-1]）。

//辗转相除法求最大公约数
function GCD(Nr1,Nr2:Integer):integer;
var
Temp:Integer;
begin
while Nr2<>0 do
begin
Temp:=Nr2;
Nr2:=Nr1 mod Temp;
Nr1:=Temp;
end;
Result:=Nr1;
end;

// 作者： creation_zy
// 时间： 2003-06
// 功能： 计算座标分别为x,y，步长分别为m,n的两只青蛙，在长度为L的纬线上
// 跳跃直至相遇所需的步数
// 返回： 返回值为所需步数，如果不能相遇，则返回-1
function GetJumpStep(x,y,m,n,L:integer):Integer;
var
i,a,b,c,temp,k,PubGCD:Integer;
begin
Result:=-1;
//统一跳跃方向
if m<0 then m:=L+(m mod L);
if n<0 then n:=L+(n mod L);
//将步长范围限制在0..L-1
m:=m mod L;
n:=n mod L;
if m<n then //swap
begin
temp:=m;
m:=n;
n:=temp;
temp:=y;
y:=x;
x:=temp;
end;
//将x,y限制在0..L-1
if x<0 then x:=L+(x mod L) else x:=x mod L;
if y<0 then y:=L+(y mod L) else y:=y mod L;
//让慢者在快者之前
if y<x then
y:=y+L;

if x=y then //位置相同
begin
Result:=0;
exit;
end;

c:=m-n;
if c=0 then //间距不会变化，无解
exit;

b:=(y-x) mod c;
if b=0 then
begin
Result:=(y-x) div (m-n);
exit;
end;

a:=L mod c;
if a=0 then //套圈后间距仍然不会变化，无解
exit;

//为了减少循环次数，将a、b、c同除以它们的最大公约数
PubGCD:=GCD(GCD(a,c),b);
if PubGCD>1 then
begin
a:=a div PubGCD;
c:=c div PubGCD;
b:=b div PubGCD;
end;

//将 (i*a + b) mod c=0 化为 (k*c - b) mod a =0 以减少循环次数
for k:=1 to a do
begin
if (k*c-b) mod a=0 then
begin
i:=(k*c-b) div a;
Result:=(i*L+(y-x)) div (c*PubGCD);
break;
end;
end;
end;

呵呵，看 creation-zy 兄的回贴就向看书一样，爽！

实际上这个问题还是求方程：
ax-by=c
的整数解问题，因为遇到素数问题，因此算法复杂度不会低于O(L)，
不可能降低到O(1)的程度。

谢谢大家的解答！