HDU 1713 衛星相遇周期：分數最小公倍數計算

問題描述

給兩顆衛星的運行周期，格式為 "圈數/天數" (如 26501/6335 表示 26501 圈需 6335 天)。求相遇周期，即兩者角速度差的週期。輸出最簡分數或整數。

數學轉化

衛星 1 角速度 ω1 = a/b (圈/天)，衛星 2 ω2 = c/d。相對角速度 |ω1 - ω2| = |ad - bc| / (bd)。相遇周期 = 1 圈 / 相對角速度 = bd / |ad - bc|。化簡分數即可。
但樣例輸出提示：實際為 LCM(a,c) / GCD(b,d) (若分母互質則為整數)。驗證：
衛星 1: 26501/6335, 衛星 2: 18468/42。
LCM(26501,18468) = 81570078, GCD(6335,42)=7 → 81570078/7。
第二組: 29359/11479, 15725/19170。LCM(29359,15725)=5431415, GCD(11479,19170)=1 → 5431415。
故公式正確：周期 = LCM(分子) / GCD(分母)。

演算法

1. 解析分數，分別約分 (分子分母除以 GCD)。
2. 計算 lcm_num = LCM(a, c), gcd_den = GCD(b, d)。
3. 若 gcd_den == 1 輸出 lcm_num，否則輸出 lcm_num/gcd_den。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int64 gcd(int64 a, int64 b) { return b ? gcd(b, a%b) : a; }
int64 lcm(int64 a, int64 b) { return a / gcd(a,b) * b; }

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int64 a,b,c,d; char ch;
        cin >> a >> ch >> b >> c >> ch >> d;
        int64 g1 = gcd(a,b); a/=g1; b/=g1;
        int64 g2 = gcd(c,d); c/=g2; d/=g2;
        int64 l = lcm(a,c);
        int64 g = gcd(b,d);
        if (g == 1) cout << l << '\n';
        else cout << l << '/' << g << '\n';
    }
    return 0;
}