思路:
有题目可以得出(mt + x) mod L = (nt + y) mod L,这样才可以相遇,因为比如1 mod 2 = (1 + 2 * n) mod 2,所以就有了(mt + x) + k * L = (nt + y)转之后就有了(m - n) * t + k * L = y - x,我们可以将之看成ax + by = c,从而使用扩展欧几里德定理。
由扩展欧几里德定理可以得出x, y, gcd(a, b)的值,由于欧几里德的公式是ax + by = gcd(a, b),但是本题需要求的是ax + by = c, 所以就有了 (ax + by) * c / gcd = gcd * c / gcd; 所以就要x * c / gcd,而且x的通解是x +k * b / gcd,所以就要取模b / gcd才能得到最小x, 而且得出的x有怕是负数,所以就有了x = (x % (b / gcd) + b / gcd) % (b / gcd);
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; ll Exgcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1; y = 0; return a; } ll r = Exgcd(b, a % b, x, y); ll t = x; x = y; y = t - a / b * y; return r; } int main() { ll x, y, m, n, l; scanf("%lld %lld %lld %lld %lld", &x, &y, &m, &n, &l); ll a = m - n; ll b = l; ll c = y - x; if (a < 0) { a = -a; c = -c; } ll gcd = Exgcd(a, b, x, y); if (c % gcd != 0) printf("Impossible"); else { x = x * c / gcd; b /= gcd; x = (x % b + b) % b; printf("%lld", x); } return 0; }