目录

题目-青蛙的约会

在这里插入图片描述
在这里插入图片描述

问题分析

因为青蛙是同时跳的, 假设同时跳 t 1 t_1 t1​次数, 那么有 ( n − m ) t 1 ≡ x − y ( m o d    L ) (n - m) t1 \equiv x - y (\mod L) (n−m)t1≡x−y(modL)
对方程进行转化
( n − m ) ⋅ t 1 + L ⋅ t 2 = x − y (n - m) \cdot t_1 + L \cdot t_2 = x - y (n−m)⋅t1​+L⋅t2​=x−y

算法步骤

首先使用扩展欧几里得算得到 ( t 1 , t 2 ) (t_1, t_2) (t1​,t2​), 无解的情况就是 d d d无法整除 x − y x - y x−y, 然后计算出 t 1 t_1 t1​的最小正整数解

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL p1, p2, n, m, L;

LL exgcd(LL a, LL b, LL &x, LL &y) {
   
    if (!b) {
   
        x = 1, y = 0;
        return a;
    }
    
    LL _x, _y;
    LL d = exgcd(b, a % b, _x, _y);
    x = _y, y = _x - (a / b) * _y;
    return d;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> p1 >> p2 >> n >> m >> L;
    LL x, y;
    LL d = exgcd(n - m, L, x, y);
    
    LL val = ((p2 - p1) % L + L) % L;
    if (val % d) {
   
        printf("Impossible\n");
        return 0;
    }
    
    x = (p2 - p1) / d * x;
    val = abs(L / d);
    x = (x % val + val) % val;
    
    cout << x << '\n';
    return 0;
}