欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ1477
题意概括
两只青蛙，现在分别在x,y的位置，以m,n的速度在周长为L的环形跑道上面跑。
问他们什么时候可以到同一个位置。（如果永远不能，则输出Impossible）
题解
扩展欧几里德模板题。
设 a = x - y , b = n - m ,
我们可以列出方程： ax ≡ b (mod L) （注意这里的x是一个未知数，不是读入的）
然后写成二元一次方程的形式： ax + Ly = b
于是exgcd跑一跑就可以了。
代码
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long LL;
LL x,y,n,m,L,a,b,c,g;
LL ex_gcd(LL a,LL b,LL &x,LL &y){
if (b==0){
x=1,y=0;
return a;
}
LL res=ex_gcd(b,a%b,y,x);
y-=(a/b)*x;
return res;
}
int main(){
scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L);
// ax = b (mod c)
// ax + by = c
a=n-m,b=L,c=x-y;
g=ex_gcd(a,b,x,y);
if (c%g){
puts("Impossible");
return 0;
}
c/=g;
x=(x*c%b+b)%b;
printf("%lld",x);
return 0;
}