Description
求n个整数的最小公倍数
Input
多组测试数据，先输入整数T表示组数 然后每行先输入1个整数n,后面输入n个整数k1 k2...kn
Output
求k1 k2 ...kn的最小公倍数
Sample Input
1
3 12 18 6
Sample Output
36
#include<stdio.h>
int gcd(int x,int y)
{
int t=;
while(t!=)
{
t=x%y;
x=y;
y=t;
}
return x;
}
int lcm(int s[],int n)
{
int num,i;
for(i=;i<n-;i++)
{
num=gcd(s[i],s[i+]);
s[i+]=s[i]/num*s[i+]/num*num;
}
return s[n-];
}
int main()
{
int t,n,m,i;
while(scanf("%d",&t)!=EOF)
{
while(t--)
{
scanf("%d",&n);
int s[n];
for(i=;i<n;i++)
{
scanf("%d",&s[i]);
}
m=lcm(s,n);
printf("%d\n",m);
}
}
}
#include <stdio.h>
/* 欧几里得算法求 数字 a b 的最大公约数 */
int gcd(int a,int b)
{
if(a<b)
{
return gcd(b,a);
}
else if(b==)
{
return a;
}
else
{
return gcd(b,a%b);
}
} /* 数字 a b 的最小公约数 */
int lcm(int a,int b)
{
return a/gcd(a,b)*b; //需要先除再乘，不然int会崩溃
} int main()
{
int n,i,r,t;
int data[n];
while(scanf("%d",&t)!=EOF)
{
while(t--)
{
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%d",&data[i]);
}
// 特殊处理只有一个数字的情况
if(n==)
{
r = data[];
}
else
{
// 先求前两个数字的最小公倍数
r = lcm(data[],data[]);
// 求第 i 个数字和前面所有数字的最小公倍数
for(i=;i<n;i++)
{
r = lcm(r,data[i]);
}
}
printf("%d\n",r);
}
}
return ;
}