两只兔子跳远相遇距离计算 - 最小公倍数算法

两只兔子跳远相遇距离计算 - 最小公倍数算法

问题描述

两只小兔子比赛跳远, 兔子A每次能跳X米，兔子B每次能跳Y米，他们同时从起点出发，在相同直线上不停的跳，请问他们下一次脚印相遇离起点有多远。

输入形式

第一行输入一个整数N表示测试用例的数量 第2行到第N+1行每行包括两个整数X,Y，表示每个用例二只兔子跳的距离，英文空格分开。

输出形式

每一行输出一个整数表示结果

样例输入

2
6 9
5 10

样例输出

18
10

样例说明

有二个用例，一个是A跳6米，B跳9米，在18米处脚印相遇。另一个用例是A跳5米，B跳10米，在10米处脚印相遇。

提示：求X，Y的最小公倍数。先输入2，表示有二组数据。接着输入 6和9，得结果18，接着输入5和10，得结果10. 程序结束。

用二重循环。

问题分析

题目要求求出两只兔子下一次脚印相遇离起点的距离，即求出两只兔子跳跃的最小公倍数。

解决思路

根据题目的要求，我们可以使用两只兔子跳跃的距离分别除以它们的最大公约数，然后再乘以它们的最小公倍数，即可得到它们下一次脚印相遇离起点的距离。

伪代码

1. 读取测试用例的数量N
2. 循环N次，对于每个测试用例执行以下操作： 3. 读取兔子A的跳跃距离X和兔子B的跳跃距离Y 4. 计算X和Y的最大公约数GCD和最小公倍数LCM 5. 计算下一次脚印相遇离起点的距离：LCM = (X / GCD) * Y 6. 输出结果LCM

代码实现

import math

# 读取测试用例的数量N
N = int(input())

# 循环N次，对于每个测试用例执行以下操作：
for _ in range(N):
    # 读取兔子A的跳跃距离X和兔子B的跳跃距离Y
    X, Y = map(int, input().split())

    # 计算X和Y的最大公约数GCD和最小公倍数LCM
    GCD = math.gcd(X, Y)
    LCM = (X // GCD) * Y

    # 输出结果LCM
    print(LCM)

复杂度分析

假设N为测试用例的数量，X和Y分别为两只兔子的跳跃距离。

时间复杂度：O(N * log(min(X, Y)))，其中log(min(X, Y))为求最大公约数的时间复杂度。 空间复杂度：O(1)。