HDOJ 1713 相遇周期

这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。

题目地址： http://acm.hdu.edu.cn/showproblem.php?pid=1713

一次AC，感觉不错。思路：说白了就是分数的GCD. 输入 a/b c/d 转换后变成： (ad)/(bd) 和 (cb)/(bd) 按照题意，就是在转相同的圈子(bd圈)时，各自需要时间ad和cb. 所以，这里把ab与cb的最小公倍数求出来就可以了。这样。求出的最小公倍数lcm再除以(bd)就是所求的周期。 (http://www.wutianqi.com/) 但是，这里要求若无法整出，则写出分数形式，这时，就可以求lcm与(bd)的最大公约数gcd, 求出gcd后与(bd)比较，若相等，则证明可以整除~~~~ 然后就可以AC了。。。

个人感觉这题对lcm,gcd考察的比较灵活，是一道好题！

// Author: Tanky Woo
// HDOJ 1713
// Accepted 1713 0MS 200K 691 B C++ Tanky Woo 
#include 
#include 
#include 
using namespace std;

__int64 gcd(__int64 a, __int64 b)
{
    if(a<b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }
    if(b == 0)
        return a;
    return gcd(b, a%b);
}

__int64 lcm(__int64 a, __int64 b)
{
    return a/gcd(a, b)*b;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int nCases;
    scanf("%d", &nCases);
    for(int i=0; i<nCases; ++i)
    {
        char tmp;
        __int64 a, b, c, d;
        scanf("%I64d/%I64d %I64d/%I64d", &a;, &b;, &c;, &d;);
        __int64 m=a*d, n=b*c, p=b*d;
        __int64 k=lcm(m, n);
        int h = gcd(k, p);
        if(p==h)
            printf("%I64d\n", k/h);
        else
            printf("%I64d/%I64d\n", k/h, p/h);
    }
    return 0;
}