本文共 1370 字，大约阅读时间需要 4 分钟。
为了解决两只青蛙相遇的问题，我们需要找到它们第一次碰面的跳跃次数。青蛙A和青蛙B分别从不同的起点出发，朝西跳，青蛙A每次跳m米，青蛙B每次跳n米。纬度线的总长度是L米。我们需要找到它们第一次碰面的时间t。
问题分析：两只青蛙的位置随着时间t变化而变化。青蛙A的位置是x + mt，青蛙B的位置是y + nt。它们碰面的条件是它们的位置相差L的整数倍，即 (x + mt) ≡ (y + nt) (mod L)。这个条件可以转化为 (m - n)*t ≡ (y - x) (mod L)。
数学建模：我们需要解同余方程 (m - n)*t ≡ (y - x) (mod L)。使用扩展欧几里得算法来求解这个方程。
扩展欧几里得算法：计算d = gcd(m - n, L)。如果 (y - x) 不是d的倍数，则无解，输出“Impossible”。否则，求解最小的正整数t。
计算最小t：根据扩展欧几里得的结果，找到t的最小正整数解，并对结果进行调整确保t为正。
def extended_gcd(a, b): if b == 0: return a, 1, 0 else: g, x, y = extended_gcd(b, a % b) return g, y, x - (a // b) * ydef solve(x, y, m, n, L): d = m - n target = y - x g, x_gcd, y_gcd = extended_gcd(d, L) if target % g != 0: return (False, 0) t0 = (target // g) * x_gcd t0 = (L - t0) % L + L # Ensure t0 is positive t = (x_gcd * target // g + y_gcd * L // g) % L return (True, t)import sysdef main(): for line in sys.stdin: x, y, m, n, L = map(int, line.strip().split()) found, t = solve(x, y, m, n, L) if found: print(t) else: print("Impossible")if __name__ == "__main__": main() 扩展欧几里得函数：用于计算最大公约数和贝祖系数，返回三个值g, x, y，使得g = gcd(a, b)，且 ax + by = g。
solve函数：计算是否存在解，并返回最小的t。使用扩展欧几里得算法解同余方程，检查是否有解，计算最小的正t。
main函数：读取输入，调用solve函数处理每个测试用例，输出结果。
这个方法利用了扩展欧几里得算法高效地解决线性同余方程问题，确保了计算的正确性和效率。
转载地址：http://pkxfk.baihongyu.com/