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

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

链接

BZOJ 1477
Tyvj 2366

题解

设两只青蛙跳了 t 次后碰面,则有:

\cases{x+tm=k_{1}*L \\ y+tn=k_{2}*L}

k=k_{1}-k_{2} ,得

(x+tm)-(y+tn)=kL

移项,得

(x-y)+(m-n)t=kL \\ (m-n)t+(-L)k=y-x

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

扩展欧几里得直接上即可,注意细节,注意细节,注意细节!

代码

#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;
}