ZOJ Problem Set - 1797
Least Common Multiple
Time Limit: 1 Second
Memory Limit: 32768 KB
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
Submit
Status
Code
//1807615 2009-03-28 09:51:26 Wrong Answer 1797 C++ 0 184 Wpl //1807641 2009-03-28 09:59:03 Accepted 1797 C++ 0 184 Wpl //注意用long long#include <iostream>using namespace std;long long gcd(long long a,long long b) //求出最大公约数{ long long i; if(a==0||b==0) //如果a和b之中有一个是0,则最大公约数就是0 return 0; if(a<b) //进行交换将a和b中大的给a小的给b { i=a; a=b; b=i; } while(a%b) //辗转相除的核心,求最大公约数 { i=a%b; a=b; b=i; } return b; //b就是最大公约数}int main() { int t,n,i; long long s,b; scanf("%d",&t); while(t--) { scanf("%d",&n); scanf("%lld",&s); for(i=1;i<n;i++) { scanf("%lld",&b); //输入一个b long long temp=gcd(s,b); if(temp==0) //如果最大公约数是0,那么最小公倍数就是0 s=0; else s=s*b/temp; //最大公约数是temp,那么最小公倍数就是a*b/temp(求a和b的最小公倍数) } printf("%lld\n",s); } return 0; }
转载于:https://www.cnblogs.com/forever4444/archive/2009/05/11/1454507.html
