hdu 1713 相遇周期 （GCD & LCM）

相遇周期

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1943 Accepted Submission(s): 1000


Problem Description 2007年3月26日，在中俄兩國元首的見證下，中國國家航天局局長孫來燕與俄羅斯聯邦航天局局長別爾米諾夫共同簽署了《中國國家航天局和俄羅斯聯邦航天局關於聯合探測火星-火衛一合作的協議》，確定中俄雙方將於2009年聯合對火星及其衛星“火衛一”進行探測。

而衛星是進行這些探測的重要工具，我們的問題是已知兩顆衛星的運行周期，求它們的相遇周期。

Input 輸入數據的第一行為一個正整數T, 表示測試數據的組數. 然後是T組測試數據. 每組測試數據包含兩組正整數，用空格隔開。每組包含兩個正整數，表示轉n圈需要的天數(26501/6335，表示轉26501圈要6335天)，用'/'隔開。

Output 對於每組測試數據, 輸出它們的相遇周期，如果相遇周期是整數則用整數表示，否則用最簡分數表示。

Sample Input

2
26501/6335 18468/42
29359/11479 15725/19170

Sample Output

81570078/7
5431415

解析：兩周期分別為a/b、c/d，既然是相遇周期，就是最早什麼時間相遇，也就是兩者的最小公倍數，轉化一下，也就是求LCM（a, c）/ gcd（b, d）。直接求即可，不一定要用long long 或者 __int64，int也能過。注意：先把a/b和c/d盡可能的化簡再求。

AC代碼：

#include 
#include 
using namespace std;

long long gcd(long long a, long long b){
    return b ? gcd(b, a % b) : a;
}

int main(){
//	freopen("in.txt", "r", stdin);
	int t;
	long long a, b, c, d, x, y;
	scanf("%d", &t);
	while(t--){
		scanf("%lld/%lld", &a, &b);
		scanf("%lld/%lld", &c, &d);
		long long fo = gcd(a, b);
		a /= fo;                  //化簡
		b /= fo;
		fo = gcd(c, d);
		c /= fo;
		d /= fo;
		x = (a * c) / gcd(a, c);              //LCM(a, c)
		y = gcd(b, d);
		if(x % y) printf("%lld/%lld\n", x, y);
		else printf("%lld\n", x / y);
	}
	return 0;
}