两仪剑法是武当派武功的高级功夫,且必须 2 个人配合使用威力才大。同时该剑法招数变化太快、太多。设武当弟子甲招数变化周期为 n,武当弟子乙招数变化周期为 m,两弟子同时使用该剑法,当 2 人恰好同时达到招数变化周期结束时,威力最大,此时能将邪教妖人置于死地。请你计算威力最大时,每人用了多少招?
输入格式
首先输入一个t(t<100000) 表示测试组数。
接下来 t 组输入,每组输入 2 个数n,m(1≤n,m≤1000000000)。
输出格式
对于每组输出,输出用了多少招数。
样例输入
3
2 3
8 9
4 8
样例输出
6
72
8解题思路:
本题明显是要求两个数的最小公倍数,我们可以先求其最大公约数k:
1.如果k=1,说明这两个数互质,则他们的最小公倍数即为他们的乘积.
2.如果k等于其中一个数,说明这个数是另一个数的因数,所以他们的最小公倍数即为较大的那个数
3.如果k不满足以上两点,则这两个数的最小公倍数即为他们与k的商的乘积再乘k.AC代码:
#include<cstdio>
#include<algorithm>
#define max(n,m) (n > m) ? n : m long long n,m,t; using namespace std; int main()
{
scanf("%lld",&t);
for(int i = ;i <= t; i++) {
scanf("%lld%lld",&n,&m);
int k = __gcd(n,m);
if(k == ) printf("%lld\n",n * m);
else if(k == n || k == m) printf("%lld\n",max(n,m));
else printf("%lld\n",(n / k) * (m / k) * k);
}
return ;
}