这篇博客是从旧博客 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;
}