「BZOJ 1477」青蛙的约会 - 扩展欧几里得

发表于 | 分类于

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

链接

BZOJ 1477
Tyvj 2366

题解

设两只青蛙跳了 次后碰面，则有：

令 ，得

移项，得

题目转化为求一个二元一次不定方程的最小正整数解。

扩展欧几里得直接上即可，注意细节，注意细节，注意细节！

代码

#include <cstdio>

const long long MAXX = 2000000000;
const long long MAXY = 2000000000;
const long long MAXN = 2000000000;
const long long MAXM = 2000000000;
const long long MAXL = 2100000000;

void exgcd(long long a, long long b, long long &g, long long &x, long long &y) {
    if (b == 0) {
        g = a;
        x = 1, y = 0;
    } else {
        exgcd(b, a % b, g, y, x);
        y -= x * (a / b);
    }
}

inline bool solve(long long a, long long b, long long c, long long &x, long long &y) {
    if (b < 0) a = -a, b = -b, c = -c;
    long long g;
    exgcd(a, b, g, x, y);
    if (c % g != 0) return false;
    x = x * c / g;
    y = y * c / g;
    long long newx = ((x % b) + b) % b;
    y = y - ((newx - x) / (b / g)) * (a / g);
    x = newx;
    return true;
}

int main() {
    long long x, y, m, n, l;
    scanf("%lld %lld %lld %lld %lld", &x, &y, &m, &n, &l);

    long long t, k;

    if (!solve(m - n, -l, y - x, t, k)) puts("Impossible");
    else printf("%lld\n", t);

    return 0;
}