【HDU 1713】相遇周期

相遇周期(题目链接)

思路

• 题目中所求的最小周期为两个分数的最小公倍数
• 求分数的最小公倍数
  • 先将两个分数通分
  • 所求数的分子是通分后的两个分数的分子的最小公倍数
  • 所求数的分母是通分后的分母（通分后两个分数分母相同）
  • 最后将计算出的分数约分

但是，笔者认为该题的描述是错误的，题目当中对分数的解释并不是周期。周期为每圈所花费的时间（单位为 天/圈），而题目中的分数的意义为每天能转多少圈（单位为 圈/天）。

代码

#include <iostream>
using namespace std;

//求最大公约数 
long long gcd(long long a, long long b){
    long long tmp = a % b;
    if(tmp == 0){
        return b;
    }
    return gcd(b, tmp);
}
 
//求最小公倍数 
long long lcm(long long a, long long b){
    return (a * b) / gcd(a, b);
}

int main(){
    char tmp;
    long long n, t, a1, b1, a2, b2, c, d;
    cin >> n;
    
    while(n--){
        cin >> a1 >> tmp >> b1 >> a2 >> tmp >> b2;  
        c = lcm(a1*b2, b1*a2);      //计算分子 
        t = gcd(c, b1 * b2);                //计算分子分母最大公约数 
        d = b1 * b2 / t;                        //分母约分 
        c /= t;                     //分子约分 
        if(d == 1){                 //判断分母是否为 1 
            cout << c << endl;
        }else{
            cout << c << tmp << d << endl;
        }
    }
        
    
    return 0;
}