青蛙的约会

Description

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

Input

输入只有一行：$5$个整数$x$，$y$，$m$，$n$，$L$，

其中$x \neq y < 2e9$，$0 < m、n < 2e9$，$0 < L < 2.1 * 10^{9}$。

Output

输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"。

Sample Input

1 2 3 4 5

Sample Output

4

Analysis

假设时间$t$后相遇，那么此时青蛙$A$的坐标为$x^{'}=(x+tm)\%L$，青蛙$B$的坐标为$y^{'}=(y+tn)\%L$。且有$x^{'}=y^{'}$，即：

$x+tm \equiv y+tn(mod \; L)$ $t(m-n) \equiv y-x(mod \; L)$

令$a=m-n$，$x=t$，$b=y-x$，$m=L$，该问题变为求解一次同余方程$ax \equiv b(mod \; m)(m > 0)$。请注意，在正式求解前，我们需要进行如下变换：

$a = (a \% m + m) \% m$，$b = (b \% m + m) \% m$，

即将$a$和$b$映射到$[0, m)$的非负数区间上，这样做是为了保证接下来求得的$a$和$b$的公约数为正数（为什么$\gcd(a, m)$要求是正数？下面再说），且在模$m$的条件下解$x$不变。

令$d=\gcd(a, m)$，先给出两个定理：

定理1：若$d \nmid b$，则该方程无解。

定理2：若$d \mid b$，则该方程有$d$个解。并且，若$\alpha x \equiv \beta (mod \; m^{'})$的唯一最小正整数解为$r$，那么，$ax \equiv b(mod \; m)$的$d$个解为 ${ x | r + km^{'} },k=0,1...d-1$ 其中$\alpha=\frac{a}{d},\beta=\frac{b}{d},m^{'}=\frac{m}{d}$。

注意到：解的间隔为$\frac{m}{d}$，那么最小正整数解一定有$r \in [0, \frac{m}{d})$。

至于证明，将在文章的末尾给出。

对于计算机来说，定理1和2可以结合计算，具体如下：

利用$exgcd$扩展欧几里得算法可得$d=exgcd(a, m, x, y)$，其中$d = \gcd(a, m)$，即$\quad \exists x, y \; \mathrm{s.t.} \;ax + my = d$， $\qquad ax \equiv d(mod \; m)$，那么$ax \cdot \frac{b}{d} \equiv d \cdot \frac{b}{d}(mod \; m)$，即$\quad a \cdot (x \cdot \frac{b}{d})\equiv b(mod \; m)$，令$x^{'}=x \cdot \frac{b}{d}$，

那么$x^{'}$就是我们最终要得到的解了！吗？当然不是！！！

请注意：采用$exgcd$算法得到的系数$x$有可能是负的，由于$b$和$d$是非负的（对应了上文为什么要求 $d$是正数），所以$x^{'}$有可能是负的，由定理2可知，令$t = \frac{m}{d}$，最小正整数解应为$(x^{'} \% t + t) \% t$。

至此，终于完成对本题的分析，相信你一定能够写出代码，参考代码如下。

Code

#include 
<iostream>
#include 
<algorithm>
#define endl "\n"

using namespace std;
typedef long long LL;

LL exgcd(LL a, LL m, LL &x, LL &y) {
    if(m == 0) {
        x = 1;
        y = 0;
        return a;
    }

    LL _x, _y;
    LL d = exgcd(m, a % m, _x, _y);
    x = _y;
    y = _x - a / m * _y;

    return d;
}

int main() {
    LL x, y, m, n, L;
    cin >> x >> y >> m >> n >> L;

    LL a = ((m - n) % L + L) % L;
    LL b = ((y - x) % L + L) % L;
        m = L;

    int d = exgcd(a, L, x, y);       
    LL t = L / d;

    if(b % d) puts("Impossible");                    
    else cout << (x * (b / d) % t + t) % t << endl;  

    return 0;
}

证明

定理一：若$d∤b$，则该方程无解，即一次同余方程$ax≡c (mod \;m)$有解的充分必要条件是$gcd(a,m)|c$。

（1）充分性：

记$d=gcd(a,m)$，$a=da_1$，$m=dm_1$，$c=dc_1$，

其中$a_1$与$m_1$互素，则存在$x_1$和$y_1$使得$a_1x_1+m_1y_1=1$。

令$x=c_1x_1$，$y=c_1y_1$，得$a_1x+m_1y=c_1$。

等式两边同乘$d$，得$ax+my=c$。

所以，$ax≡c(mod \; m)$，即$x$是方程的解。

（2）必要性：

设$x$是方程的解，则存在$y$使得$ax+my=c$。

则由性质：如果$a|b$且$a|c$，则对任意的整数$x,y$，有$a|xb+yc$得，有$d|c$.

设$x_0$是方程的解，不难验证所有与$x_0$模$m$同余的数都是方程的解，从而方程的解可以写成$x≡x_0(mod \; m)$。

于是，只需对模$m$的每一个等价类取一个代表，验证是否使方程成立，就能找到方程的所有的解。

定理二：设$m>0$，$d=\gcd(a,m)$且$d|c$，证明：一次同余方程$ax≡c(mod \; m)$在模$m$下有$d$个解。

证明如下：

设$a=da_1$，$m=dm_1$，其中设$a_1$，$m_1$互素。

根据定理，存在$x_0$，使$ax_0≡c(mod\; m)$，又设$x$是方程的解，即$ax≡c(mod \; m)$。

于是，$a(x-x_0)≡0(mod \; m)$，它等价于$a_1(x-x_0 )≡0(mod \; m_1 )$，

而$a_1$与$m_1$互素，故有$x-x_0≡0(mod \;m_1 )$。

因此，方程在模$m$下恰好有$d$个解$x≡x_0 + km_1 (mod \; m_1),\quad k=0,1,…,d-1$。