不想算了这两只青蛙永远也走不到一起了

咳咳，我们的任务是帮助这两只青蛙看它们什么时候可以碰面。

输入x，y表示青蛙一开始的位置，m , n表示青蛙跳一次的距离，L表示这个数轴的总长度。

那么我们假设两只青蛙可以碰面，并且需要跳i次才能碰面，所以青蛙A就要跳m i+x的距离，青蛙B就要跳n i+y的距离，它们两个可以碰面，所以

(m i+x)%L = (n i+y) % L

通过扩展欧几里得算法可以转化成

m i + x + L * j1 = n i + y + L * j2

两边合并一下变成

( m - n )* i + L * (j1 - j2) = y - x

所以存在j = j1 - j2,使得上式成立，我们设h=m - n,f = y - x,j = j1 - j2,得到下面

h * i+ L * j = f

离扩展欧几里得的ax+by=g就差一步了，因此我们设h * i+L * j=gcd( h, L),这样就可以用欧几里得算法求出 i 了，最后输出的时候将 i 乘 f / gcd( h , L),就可以得出最后的结果

思路理完之后开码

当然在这题会出现m < n 的情况，我们就要将 m 和 n处理一下，将它改成正数

if (h < 0) {
        h = n - m;
        f = x - y;
    }

这题最后我们还需要判断我们输出的答案是否能让青蛙A和青蛙B碰面，所以我们拿出我们上面推出来的式子将 i 代进去看是否满足要求

if ((m*i+x)% L != (n*i+y)% L) {
        cout << "Impossible" << endl;
        return 0;
    }

完整代码

#include<iostream>
using namespace std;
#define ll long long
ll x, y, m, n, L, i, j, h, f, g;
void exgcd(ll a,ll b) {
    if (b == 0) {
        i = 1;
        j = 2;
        g = a;
        return;
    }
    exgcd(b, a % b);
    ll c = i; i = j;
    j = c - (a / b) * j;
}
int main()
{
    cin >> x >> y >> m >> n >> L;
    h = m - n;
    f = y - x;
    if (h < 0) {
        h = n - m;
        f = x - y;
    }
    exgcd(h, L);
    i = (f / g * i % (L / g) + L / g) % (L / g);//处理负数答案
    if ((m*i+x)%L!=(n*i+y)%L) {
        cout << "Impossible" << endl;
        return 0;
    }
    cout << i << endl; 
}

本人小白如有不对欢迎指正