POJ1061-青蛙的约会

题面描述

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经 度处为原点,由东往西为正方向,单位长度 米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是 ,青蛙B的出发点坐标是 。青蛙A一次能跳 米,青蛙B一次能跳 米,两只青蛙跳一次所花费的时间相同。纬度线总长 米。现在要你求出它们跳了几次以后才会碰面。

输入格式

输入只包括一行5个整数,其中

样例数据

样例输入

1 2 3 4 5

样例输出

4

题解

假设现在跳跃了次,那么根据题意,两只青蛙的位置分别是:

那么若有,则有:

转化为同余方程的形式,则有:

该同余方程又等价于等式:

移项,得到:

要保证该方程有解,就要保证。对于,理解为要让跑得快的青蛙的速度做被减数,那么当不满足要求时,我们直接交换两只青蛙即可。

再考虑。由于两只青蛙处于一个环形跑道上,其前后关系可以直接很容易的通过抢跑一圈来改变。反映到代码上,就是当出现时,使即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read() {
register char c = getchar();
register int f = 1, _ = 0;
while (c > '9' || c < '0')
f = (c == '-') ? -1 : 1, c = getchar();
while (c <= '9' && c >= '0')
_ = (_ << 3) + (_ << 1) + (c ^ 48), c = getchar();
return _ * f;
}
int x, y, m, n, l;

int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int r = exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * y;
return r;
}

signed main() {
int t = read();
while (t--) {
cin >> x >> y >> m >> n >> l;
if (m < n) {
swap(x, y);
swap(m, n);
}
if (y < x) {
y += l;
}
int p, q;
//cout << x << "." << y << "." << m << "." << n << "." << l << endl;
//cout << m - n << "," << l << "," << __gcd(m - n, l) << endl;
int Gd = exgcd(m - n, l, p, q);
//cout << x0 << "," << y0 << endl;
if ((y - x) % Gd != 0) {
puts("Impossible");
continue;
}
int mod = l / Gd;
p = (((p % mod) * ((y - x) / Gd % mod)) % mod + mod) % mod;
if (p < 0) {
puts("Impossible");
continue;
}
cout << p << endl;
}
return 0;
}