1 条题解

  • 0
    @ 2025-3-22 10:10:18
    #include <iostream>
    using namespace std;
    
    // 扩展欧几里得算法
    long long exgcd(long long a, long long b, long long &x, long long &y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        long long d = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
    
    // 求解青蛙碰面问题
    long long solve(long long x, long long y, long long m, long long n, long long L) {
        long long a = m - n;
        long long b = L;
        long long c = y - x;
        if (a < 0) {
            a = -a;
            c = -c;
        }
        long long x0, y0;
        long long d = exgcd(a, b, x0, y0);
        if (c % d != 0) {
            return -1;
        }
        long long mod = b / d;
        long long ans = (x0 * (c / d) % mod + mod) % mod;
        return ans;
    }
    
    int main() {
        long long x, y, m, n, L;
        cin >> x >> y >> m >> n >> L;
        long long result = solve(x, y, m, n, L);
        if (result == -1) {
            cout << "Impossible" << endl;
        } else {
            cout << result << endl;
        }
        return 0;
    }    
    

    信息

    ID
    5574
    时间
    1000ms
    内存
    125MiB
    难度
    4
    标签
    递交数
    25
    已通过
    11
    上传者