Question

ACM PKU 1061

下面是我写的java代码，但在北大编译的时候提示超时，哪位帮忙看看是什么原因，有什么改进的方法？
import java.util.*;

public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
long x = in.nextLong();
long y = in.nextLong();
long m = in.nextLong();
long n = in.nextLong();
long L = in.nextLong();
long step;
if(m==n)
System.out.println("Impossible");
else{
for(int i=1;;i++){
for( step=0;;step++){
if(Math.abs((x+m*step)-(y+n*step))==i*L){
break;
}
else if(Math.abs(m-n)*step>i*L+y-x)
continue;
}
break;

}
System.out.println(step);

}

}
}

Answer 1

青蛙的约会？

死做肯定超时

如果只是想AC，那么你可以借鉴“相对论”。就是把青蛙A的速度看为0，坐标看为0，然后把青蛙B的速度和坐标都参照青蛙A的速度和坐标来看待。然后做，这样的耗时是300MS左右（我朋友这样做了，耗时328MS，C++）。

然后如果想0MS的话，就要用到扩展欧几里德算法了。
int Euclid_Extended(int a,int b,int &x0,int &y0)
{
int t,d;
if (b==0) {
x0=1; y0=0;
return a;
}
d=Euclid_Extended(b,a%b,x0,y0);
t=x0;
x0=y0;
y0=t-a/b*y0;
return d;
}

函数返回值为gcd(a,b),并顺带解出ax+by=1的一个解x0,y0,

对于不定方程ax+by=c的通解为：
x=x0*c/d+b/d*t
y=y0*c/d+a/d*t

当c%gcd(a,b)!=0时,不定方程无解.

具体可以去看看Discuss里面的内容

Answer 2

这个是中国剩余定理的应用，用扩展欧几里德可以做出来