题意:
两只青蛙在同一条纬度上,它们各自朝西跳,问它们要跳多少步才能碰面(必须同时到达同一点).
分析:
假设它们跳了t步才相遇,青蛙a初始坐标为x,青蛙b初始坐标为y,则跳了t步相遇后a的坐标为 x+m*t-p1*l, b的坐标为 y+n*t-p2*l (p1,p2分别表示a,b跳
的圈数) x+m*t-p1*l = y+n*t-p2*l => x-y = (n-m)*t + (p1-p2)*l => x-y = (n-m)*t + p*l.
代码如下:
//方法一 #include <iostream>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <iterator>
#include <vector> using namespace std; #define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define MAXN 10000010
#define MAXM 1000010 LL extend_gcd(LL a, LL b, LL &x, LL &y)
{
if(b == )
{
x = ;
y = ;
return a;
}
else
{
LL r = extend_gcd(b, a%b, y, x);
y -= x*(a/b);
return r;
}
} int main()
{
LL x, y, m, n, l;
while(scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &l)==)
{
LL t, p;
LL ans = extend_gcd(n-m, l, t, p);
if((x-y)%ans)
printf("Impossible\n");
else
{
t = t*(x-y)/ans;
t = (t%(l/ans)+(l/ans))%(l/ans);
printf("%lld\n", t);
}
} return ;
}
//方法二 #include <iostream>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <iterator>
#include <vector> using namespace std; #define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define MAXN 10000010
#define MAXM 1000010 LL extend_gcd(LL a, LL b, LL &x, LL &y)
{
if(b == )
{
x = ;
y = ;
return a;
}
else
{
LL r = extend_gcd(b, a%b, y, x);
y -= x*(a/b);
return r;
}
} LL cal(LL a, LL b, LL c)
{
LL x, y;
LL ans = extend_gcd(a, b, x, y);
if(c%ans)
return -;
x *= c/ans;
b /= ans;
if(b < )
b = b*(-);
// b = abs(b); //abs只能对int取绝对值
ans = x%b;
if(ans <= )
ans += b;
return ans;
} int main()
{
LL x, y, m, n, l;
while(scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &l)==)
{
LL sum = cal(n-m, l, x-y);
if(sum == -)
printf("Impossible\n");
else
printf("%lld\n", sum);
} return ;
}