P1516 青蛙的约会

P1516 青蛙的约会

解关于 $k$ 的方程：
$$
x + k m \equiv y + k n (\mod l )
$$
整理一下
$$
k(n - m) \equiv x - y (\mod l )
$$
即
$$
k (n - m) + pl = x - y (p \in \mathbb N)
$$
用扩欧解即可。

查看代码

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
LL X, Y, m, n, L;
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;
}
int main ()
{
    scanf("%lld%lld%lld%lld%lld", &X, &Y, &m, &n, &L);
    if (n < m)
    {
        swap(n, m);
        swap(X, Y);
    }
    LL x, y;
    LL d = exgcd(n - m, L, x, y);
    if ((X - Y) % d)
        printf("Impossible");
    else
        printf("%lld", ((X - Y) / d * x + (L / d)) % (L / d));
    return 0;
}