首页 > 代码库 > 杭电acm2028--最小公倍数
杭电acm2028--最小公倍数
Lowest Common Multiple Plus
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 31453 Accepted Submission(s): 12802
Problem Description
求n个数的最小公倍数。
Input
输入包含多个测试实例,每个测试实例的开始是一个正整数n,然后是n个正整数。
Output
为每组测试数据输出它们的最小公倍数,每个测试实例的输出占一行。你可以假设最后的输出是一个32位的整数。
Sample Input
2 4 6 3 2 5 7
Sample Output
12 70
分析:先用辗转相除法求出最小公约数,再求最大公倍数。
1 #include<stdio.h> 2 int gcd(int a,int b) 3 { 4 //辗转相除法 5 int temp; 6 if(a<b) 7 { 8 temp=a; 9 a=b; 10 b=temp; 11 } 12 if(a%b==0) 13 return b; 14 return gcd(b,a%b); 15 } 16 int main() 17 { 18 int a,b,n; 19 while(scanf("%d",&n)!=EOF) 20 { 21 scanf("%d\n",&a); 22 if(n==1) 23 printf("%d",a); 24 else 25 { 26 n--; 27 while(n--) 28 { 29 scanf("%d",&b); 30 //防止数据越界,先相除,再相乘 31 a=b/gcd(a,b)*a; 32 } 33 printf("%d\n",a); 34 } 35 } 36 return 0; 37 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。