首页 > 代码库 > Least Common Multiple ＨＤＵ１０１９
Least Common Multiple ＨＤＵ１０１９
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.
InputInput 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.
OutputFor 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
两个两个求最小公倍数，用到辗转相除注意ａ先除最大公约在＊ｂ这样可以避免使用ｌｏｎｇｌｏｎｇ。
1 #include <iostream> 2 using namespace std; 3 #include<string.h> 4 #include<set> 5 #include<stdio.h> 6 #include<math.h> 7 #include<queue> 8 #include<map> 9 #include<algorithm> 10 #include<cstdio> 11 #include<cmath> 12 #include<cstring> 13 #include <cstdio> 14 #include <cstdlib> 15 #include<cstring> 16 int qqq(int a,int b) 17 { 18 if(a%b==0) 19 return b; 20 return qqq(b,a%b); 21 } 22 int www(int a,int b) 23 { 24 return a/qqq(a,b)*b; 25 } 26 int main() 27 { 28 int t; 29 cin>>t; 30 while(t--) 31 { 32 int n; 33 cin>>n; 34 int a,b; 35 a=1; 36 while(n--) 37 { 38 cin>>b; 39 if(b>a) 40 swap(a,b); 41 a=www(a,b); 42 } 43 cout<<a<<endl; 44 } 45 return 0; 46 }
Least Common Multiple ＨＤＵ１０１９
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。