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
23 5 7 156 4 10296 936 1287 792 1
Sample Output
10510296
int gcd(int a,int b) // 最大公约数模板{if(a<b) return gcd(b,a);int r;while(b) {r=a%b;a=b;b=r;}return a;}int lcm(int a,int b) {return a/gcd(a,b)*b;} //最小公倍数模板
此题为模板题。。。
#include<iostream>#include<cmath>#include<cstdio>using namespace std;int gcd(int a,int b) { if(a<b) return gcd(b,a); int r; while(b) {r=a%b;a=b;b=r;} return a;}int lcm(int a,int b) {return a/gcd(a,b)*b;}int main(){int t,n,i,j,num,sum;scanf("%d",&t);while(t–) {scanf("%d%d",&n,&sum);for(i=2;i<=n;i++){scanf("%d",&num);if(sum%num) {sum=lcm(sum,num);}}printf("%d\n",sum);}return 0;}
版权声明:本文为博主原创文章,未经博主允许不得转载。
,如果爱,请深爱;如不爱,请离开。