「BZOJ 1477」青蛙的约会

Descripion

环形数轴长 $L\ (0 < L < 2.1 \times 10^9)$ 米（单位长度 $1$ 米），上面有两只青蛙，向正方向跳跃，出发点分别为 $x$ 和 $y\ (0 < x \neq y < 2 \times 10^9)$，一次分别能跳 $m$ 米 和 $n$ 米 $(0 < m,n < 2 \times 10^9)$，两只青蛙跳一次所花的时间相同，求最少跳几次才能相遇。若永远不能相遇，输出 Impossible 。

Source

[BZOJ]1477

Solution

前置知识：

扩展欧几里得(exgcd)算法

假设两只青蛙跳 $a$ 步能够相遇，则有方程

$$x + am \equiv y + an \pmod L$$

根据同余式的性质，化简得到

$$(m-n)a \equiv y - x \pmod L$$

这个方程等价于

$$(m - n)a + L \times b = y - x$$

我们只有 $a$ 和 $b$ 未知，其它量都已知，这不就是一个形如 $ax + by = c$ 的 不定方程 吗？

我们可以用 exgcd（扩展欧几里得） 算法求出方程 $(m-n)a + L \times b = \gcd(m - n, L)$ 中 $a$ 的一个解 ${a}’$ 。

值得注意的是，$\gcd$ 只对 非负整数 有意义。所以一定要保证 $m \geq n$，若 $m < n$，则在 exgcd 前交换两只青蛙的信息即可。

如果方程 $(m - n)a + L \times b = y - x$ 有解，则一定满足 $y - x \mid \gcd(m - n, L)$，否则无解（输出 Impossible）。

若方程有解，则 $a$ 实际的解为 ${a}’ \times \frac{y-x}{\gcd(m - n, L)}$，可这只是这个不定方程的特解，不一定是最小正整数解。

我们让 $L = \frac{L}{\gcd(m - n, L)}$，最小正整数解即为 $\left( a \bmod L + L\right) \bmod L$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

LL exGcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    LL d = exGcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

LL x, y, m, n, l, d, a, b;

int main() {
    read(x), read(y), read(m), read(n), read(l);
    if (m < n) {
        swap(m, n);
        swap(x, y);
    }//m < n，则交换两只青蛙的信息 
    d = exGcd(m - n, l, a, b);//扩展欧几里得求解不定方程，其中 d = gcd(m - n, L) 
    if ((y - x) % d == 0) {
        a *= (y - x) / d;//a 实际的解 
        l /= d;
        write((a % l + l) % l);
        putchar('\n');
    } else puts("Impossible");//无解 
    return 0;
}