Least Common Multiple

101 阅读 0 评论 67 点赞

我是靠谱客的博主跳跃犀牛，最近开发中收集的这篇文章主要介绍Least Common Multiple，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述


下面为 学长 大家公认的水题， 我比水题还睡 的 WA 了三遍 才成功在好队友的帮助下，A 了

杭电HDU Least Common Multiple
Problem Description
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105.

Input
Input will consist of multiple problem instances. The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 … nm where m is the number of integers in the set and n1 … nm are the integers. All integers will be positive and lie within the range of a 32-bit integer.

Output
For each problem instance, output a single line containing the corresponding LCM. All results will lie in the range of a 32-bit integer.

Sample Input
2
3 5 7 15
6 4 10296 936 1287 792 1

Sample Output
105
10296

Source
East Central North America 2003, Practice

Recommend
JGShining

队友写的：点击有惊喜哦！代码链接
我写的：

#include <bits/stdc++.h>
using namespace std;
// 记住， 这是一道水题 坑
int zhan(int a, int b)
{
if(a < b) // 习惯比较一下大小的 哈哈哈
{
int temp = a; a = b; b = temp;
}
int c = a,f = b; // 先保存a，b，的值
while(b != 0)
{
int r = a % b;
a = b;
b = r;
}
return c / a * f; //这里如果先乘后除的话，可能会出现超出int限制的数
}
int main()
{
int T, n, a[1000]; // 还可以不开数组的换成读取一个一个的a
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
scanf("%d",&a[i]);
}
if(n > 1) // 因为我这样做很low啊， 所以判断了n > 1 的情况
{
int t = zhan(a[0],a[1]);
for(int i = 2; i < n;)
{
t = zhan(t,a[i++]);
}
printf("%dn",t);
}
else
printf("%dn",a[0]); // 若是一个数， 就输出，我单独判断了， 显得很low， 水娃
}
return 0;
}