HDU 1713(相遇周期)求分数的最小公倍数!

spoiler posted @ 2011年4月16日 20:04 in 未分类 , 2630 阅读

题目分析:题目输入c1/t1 c2/t2 ,也就是速度的分数形式,转换成:c1*t2/(t1*t2),  c2*t1/( t1*t2 ); 这时候我们只需要求出分子的最小公倍数k,然后k/( t1*t2 )就是题目求的周期

代码+部分注释:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
__int64 gcd(__int64 a,__int64 b){
	__int64 c;
	if(a<b){
		c=a;	a=b;
		b=c;
	}
	while(b){
		c=b;
		b=a%b;
		a=c;
	}
	return a;
}
__int64 min_times(__int64 x1,__int64 x2){
	__int64 c=gcd(x1,x2);
	return x1*x2/c;
}
int main(){
	__int64 cas,c1,c2,t1;
	__int64 t2,p,k,m,n,h;
	cin>>cas;
	while(cas--){
		scanf("%I64d/%I64d",&c1,&t1);
                 //在这里提醒一下,用long long型的过不了!
                 //因为这个WA的好多次!
		scanf("%I64d/%I64dd",&c2,&t2);
		k=t1*t2;
		m=t2*c1;
		n=t1*c2;
		p=min_times(m,n);
		h=gcd(p,k);
		if(h==k){
			printf("%I64d\n",p/h);
		}
		else{
			printf("%I64d/%I64d\n",p/h,k/h);
		}
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter