HDU - 相遇周期
而卫星是进行这些探测的重要工具，我们的问题是已知两颗卫星的运行周期，求它们的相遇周期。
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
#include <stdio.h>#define ll long longll gcd(ll m,ll n)//最大公因数{ll t;if(m<n){t=m;m=n;n=t;}while(n>0){t=m;m=n;n=t%n;}return m;}ll lcm(ll m,ll n)//最小公倍数{return m*n/gcd(m,n);}int main(){int T;ll a,b,c,d,x,y;scanf("%d",&T);while(T--){scanf("%lld/%lld %lld/%lld",&a,&b,&c,&d);x=gcd(a,b);y=gcd(c,d);//约分a/=x;b/=x;c/=y;d/=y;if(gcd(b,d)==1){printf("%lld\n",lcm(a,c));}else{printf("%lld/%lld\n",lcm(a,c),gcd(b,d));}}return 0;}
大佬的简便写法（看不大懂）
LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
但是 数量级相当大（千位级别的运算）的时候似乎上面的算法执行效率并不是想象中那么快速，所以有了如下的快速GCD算法，其原理是：更相减损法，当传入的参数a和b均为偶数时，我们吧a和b全部右移（>>），然后在结尾乘2（<<），如果一个奇数，一个偶数的话我们很容易想到，2肯定不会是这两个数的公约数，所以我们把偶数右移两位（>>）， 如果两个数都是奇数的话，我们就令他们进行相减，然后再把a和b取最小的传入，就会出现一奇一偶的两个数即可进行下一步的运算； 算法C++实现如下：
int qGCD(int a, int b){if(a == 0) return b;if(b == 0) return a;if(!(a & 1) && !(b & 1)) // a % 2 == 0 && b % 2 == 0;return qGCD(a >> 1, b >> 1) << 1;else if(!(b & 1))return qGCD(a, b >> 1);else if(!(a & 1))return qGCD(a >> 1, b);elsereturn qGCD(abs(a - b), min(a, b));}
原文：/m0_38081836/article/details/78053715
