7.4宝藏
2026-07-04 11:10:36
发布于：广东
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll; // 定义 long long 为 ll，防止大数相乘溢出（数据最大 2e9，相乘达 4e18，必须用 64 位）
// ---------- 全局变量 ----------
ll x, y, m, n, l; // x:A起点, y:B起点, m:A步长, n:B步长, l:纬度总长(模数)
ll k, r, a, b; // k:整数圈数(未使用), r:最大公约数, a:初始差距, b:相对速度
int xx, yy; // 【注意隐患】这里声明为 int，但扩展欧几里得算出的系数可能极大，建议改为 ll
// 若按原代码，极端数据下 xx 或 yy 可能溢出 int，这里保持原样讲解，实战建议改成 ll
// ---------- 扩展欧几里得算法（核心） ----------
// 函数功能：求 a,b 的最大公约数 g，并求出一组整数解 (xx, yy)，使得 axx + byy = g
ll gcd(ll a, ll b, int &xx, int &yy) // 注意这里传的是 int 引用，接收全局的 xx,yy
{
// 递归边界：欧几里得算法的终点，此时 b == 0
if(b == 0)
{
// 此时等式变为 a * xx + 0 * yy = a
// 显然取 xx = 1, yy = 0 即可使等式成立 (1*a + 0 = a)
xx = 1;
yy = 0;
return a; // 返回最大公约数 a
}
// 递归向下求解：先求 gcd(b, a % b) 以及对应的系数 x', y'
// 设下一层返回时，满足： b * x' + (a % b) * y' = g
ll r = gcd(b, a % b, xx, yy);
// ---------- 回溯更新系数（最难理解的一步） ----------
// 目标：利用下一层的 (xx, yy) 推出当前层的 (xx, yy)
// 已知：a % b = a - (a / b) * b
// 代入下一层等式：b * x' + [a - (a/b)*b] * y' = g
// 展开整理：a * y' + b * [x' - (a/b)*y'] = g
// 对比当前层标准式：a * xx + b * yy = g
// 所以得到：当前 xx = y', 当前 yy = x' - (a/b)*y'
int t = xx; // t 临时存储下一层的 x'（因为等下 xx 要被覆盖）
xx = yy; // 当前 xx = 下一层的 y'
yy = t - (a / b) * yy; // 当前 yy = 下一层的 x' - (a/b) * 下一层的 y'
return r; // 返回最大公约数
}
// ---------- 主函数 ----------
int main()
{
// 1. 读入五个整数
scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &l);
// 2. 建立同余方程
// 相遇条件：(x + m*t) ≡ (y + n*t) (mod L)
// 移项得：(m - n)*t ≡ (y - x) (mod L)
// 为了让代码好处理，两边同时乘以 -1，变成：(n - m)*t ≡ (x - y) (mod L)
// 因此令：a = x - y, b = n - m
a = x - y;
b = n - m;
// 3. 调整符号（让扩展欧几里得的参数 b 为正数）
// 如果 b < 0，即 n < m（A比B跳得慢），
// 为了保证下一步计算 gcd(b, L) 时 b 为正，我们把等式两边同时乘以 -1：
// (-b)*t ≡ (-a) (mod L)，即 b 和 a 同时取反。
if(b < 0)
{
a = -a;
b = -b;
}
// 4. 调用扩展欧几里得，计算 g = gcd(b, L)，并求出 b*xx + L*yy = g 的一组解
// 注意：这里传入的是全局的 (xx, yy)，函数会修改它们
r = gcd(b, l, xx, yy);
// 5. 判断是否有解（同余方程有解判定定理）
// 方程 b*t ≡ a (mod L) 有整数解 当且仅当 gcd(b, L) 能够整除 a
// 即 a % r == 0。如果除不尽，说明两只青蛙的相对位移永远无法弥补初始差距，永远碰不到。
if(a % r != 0)
{
printf("Impossible");
return 0;
}
// 6. 计算最小非负整数解（即第一次碰面的次数）
// 6.1 先求出特解：t0 = xx * (a / r)
// 因为 b*xx + L*yy = r，两边乘以 (a/r) 得：
// b * [xx*(a/r)] + L * [yy*(a/r)] = a
// 即 b * t0 ≡ a (mod L)，所以 t0 是一个特解
ll t0 = xx * (a / r);
// 6.2 求出通解的周期（步长）
// 所有解的通式为：t = t0 + k * (L / r)
// 因为每增加 (L / r)，b*t 就增加 b*(L/r)，它恰好是 L 的 (b/r) 倍，模 L 不变。
ll mod = l / r;
// 6.3 将特解调整到 [0, mod - 1] 范围内，得到最小非负解
// 先取模，再加上 mod 再取模，是为了防止负数（C++ 负数取模仍为负数）
ll ans = ((t0 % mod) + mod) % mod;
// 7. 输出答案
printf("%lld", ans);
return 0;
}
这里空空如也
有帮助，赞一个