Least Common Multiple
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 18363 Accepted Submission(s): 6840
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
Recommend
JGShining
#include<stdio.h> int main() { int i, j, n, k, num, count = 1; int ch, p1, r, q1, p, q; scanf("%d", &n); while(n--) { i = q = p = r = 0; count = 1; scanf("%d", &num); while(num--) { scanf("%d", &ch); if(count++ == 1) {p = p1 = ch; continue;} else q = q1 = ch; if(q > p) { r = q; q = p; p = r; } while(p%q != 0) { r = q; q = p%q; p = r; } p = p1 = p1/q*q1; } printf("%d\n", p); } return 0; }
解题报告：
这题是我提交最多的一题，纠结在于不懂32-bit integer到底是什么意思，从一开始就没用int定义变量，最小公倍数 = 数之间相乘/数之间的最大公约数，思路无错，测试数据完全正确，但提交上去就不是一回事了，我用了long long，但总是WA，过段时间没辙了，discuss中找到了相似的代码，将我的代码一点一点的插入他人的代码中，一直提交着，我要看看哪里出错了，求最大公约数没错——大小数替换没错，最后干脆把注释的内容都删掉了，提交还是错误，无奈之下将所有的数改为int型，AC了！我只知道数的范围开小了会WA，但没想到开大了也会WA!
