首页 > 代码库 > GDUFE ACM-1003
GDUFE ACM-1003
题目:http://acm.gdufe.edu.cn/Problem/read/id/1003
Lowest Common Multiple Plus
Time Limit: 2000/1000ms (Java/Others)
Problem Description:
求n个数的最小公倍数。
Input:
输入包含多个测试实例,每个测试实例的开始是一个正整数n(2<=n<=100),然后是n个正整数(数字均大于0)。
Output:
为每组测试数据输出它们的最小公倍数,每个测试实例的输出占一行。你可以假设最后的输出是一个64位的整数。
Sample Input:
2 3 4 3 23 45 2
Sample Output:
12 2070
思路:先计算出两个数的最大质子数,再算出它们的最小公倍数,再用它们的最小公倍数与下一个数进行运算。
难度:要想出怎么算两个数的最小公倍数很容易,但想出怎么算n个数的就比较难了>-<
代码:
1 #include<stdio.h> 2 int main() 3 { 4 long long int n,m,a,b,k,r,d,i; 5 while(scanf("%lld",&n)!=EOF) 6 { 7 n--; 8 scanf("%lld",&m); 9 while(n--) 10 { 11 scanf("%lld",&k); 12 if(m<k) 13 { 14 a=m;m=k;k=a; 15 } 16 r=0; 17 b=m;r=k; 18 for(i=0;1;i++) 19 { 20 a=b;b=r; 21 d=r;r=a%b; 22 if(r==0) 23 break; 24 } 25 if(d!=0) 26 m=m*k/d; 27 } 28 printf("%lld\n",m); 29 } 30 return 0; 31 }
GDUFE ACM-1003
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。