The Extended Euclidean Algorithm is a fundamental tool for solving linear Diophantine equations of the form ax + by = gcd(a, b). This technique is frequently required in competitive programming to solve problems involving modular arithmetic and periodic patterns, such as the classic "Frog's Meeting" problem.

Mathematical Foundation

The Euclidean Algorithm relies on the property that gcd(a, b) = gcd(b, a % b). The Extended Euclidean Algorithm extends this to recover the coefficients x and y such that:

ax + by = gcd(a, b)

Given the recursive step gcd(a, b) = gcd(b, a % b), we can write:

b * x' + (a % b) * y' = gcd(a, b)
Since (a % b) = a - floor(a / b) * b, we substitute:
b * x' + (a - floor(a / b) * b) * y' = gcd(a, b)
a * y' + b * (x' - floor(a / b) * y') = gcd(a, b)

This allows us to compute x and y recursive by setting x = y' and y = x' - floor(a / b) * y'.

Solving Modular Equations

In scenarios where we need to find the number of steps k for two objects to meet, we often derive a linear congruence:

(n - m) * k ≡ (x - y) (mod L)

This is equivalent to the linear Diophantine equation:

(n - m) * k + L * t = (x - y)

Let A = (n - m), B = L, and C = (x - y). The equation is Ak + Bt = C. This equation has solutions if and only if gcd(A, B) divides C. If it does, we find a base solution using the Extended Euclidean Algorithm and scale it by C / gcd(A, B).

Implementation

Below is a clean implementation of the Extended Euclidean Algorithm used to find the smallest non-negative jump count:

#include <iostream>

typedef long long ll;

// Extended Euclidean Algorithm
ll extended_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x_next, y_next;
    ll gcd_val = extended_gcd(b, a % b, x_next, y_next);
    x = y_next;
    y = x_next - (a / b) * y_next;
    return gcd_val;
}

int main() {
    ll x, y, m, n, L;
    if (!(std::cin >> x >> y >> m >> n >> L)) return 0;

    ll A = n - m;
    ll C = x - y;

    // Handle negative coefficients
    if (A < 0) {
        A = -A;
        C = -C;
    }

    ll u, v;
    ll divisor = extended_gcd(A, L, u, v);

    if (C % divisor != 0) {
        std::cout << "Impossible" << std::endl;
    } else {
        ll mod = L / divisor;
        // Calculate result and ensure it is the smallest non-negative value
        ll result = (u * (C / divisor)) % mod;
        if (result < 0) result += mod;
        std::cout << result << std::endl;
    }
    return 0;
}