洛谷1516 青蛙的约会

这已经是我三刷这道题了（前两次是2017-08-09和2018-05-07），但靠自己还是没有推出来。果然这种题还是适合写个总结啊。

题意

两只青蛙分别从 $x \ , \ y$ 开始向数轴正方向跳，每 $-1s$ 可以分别跳 $m \ , \ n$ 。数轴是环形的，长度为 $l$ 。

求它们相遇最少需要续的时间，如果不能相遇输出Impossible。

题解

设续的最少时间为 $t$ ，将题意转化为

$$m\times t+x \equiv n\times t+y \ (mod \ l)$$

用 $k$ 代表等式两边差值 $\div l$ 的值，那么可以化为

$$(n-m)\times t+k\times l=x-y$$

设 $a=n-m \ , \ b=l \ , \ c=x-y$ ：

$$a\times t+b\times k=c$$

令 $g=\text{gcd}(a,b)$ ，可以先用 $\text{exgcd}$ 求出当 $c=g$ 时的解 $x_0,y_0$ ：

$$a\times x_0+b\times y_0=g \tag{1}$$

两边同时 $\times \dfrac{c}{g}$ ，得

$$a\times (\dfrac{x_0\times c}{g})+b\times (\dfrac{y_0\times c}{g})=c \tag{2}$$

也就是说原方程的其中一个解 $t=\dfrac{x_0\times c}{g}$ 。无解的情况即为 $c \ mod \ g \neq 0$ 。

要求最小的的非负整数解，即可以对 $(1)$ 式中的 $x_0$ 不断减去 $b$ ，直到刚好 $\geq 0$ 。也就是 $x_0 \ mod \ b$ 。

对于 $(2)$ 中的 $\dfrac{x_0\times c}{g}$ ，最小非负整数解即为 $\dfrac{x_0\times c}{g} \ mod \ \dfrac{b}{g}$ 。因为 $t$ 可能是负数，所以需要先 $+\dfrac{b}{g}$ 再取模。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll x,y,m,n,l;

ll exgcd(ll x,ll y,ll &X,ll &Y)
{
    if (y==0)
    {
        X=1; Y=0;
        return x;
    }
    ll ans=exgcd(y,x%y,Y,X);
    Y-=x/y*X;
    return ans;
}

int main()
{
    x=read(); y=read(); m=read(); n=read(); l=read();
    ll a=n-m,b=l,c=x-y;
    if (a<0) a=-a,c=-c;
    ll X=0,Y=0;
    ll g=exgcd(a,b,X,Y);
    if (c%g) return !printf("Impossible");
    return !printf("%lld",(X*c/g%(b/g)+b/g)%(b/g));
}