首页 > 代码库 > HDU 2028 Lowest Common Multiple Plus
HDU 2028 Lowest Common Multiple Plus
Lowest Common Multiple Plus
Problem Description
求n个数的最小公倍数。
Input
输入包括多个測试实例。每一个測试实例的開始是一个正整数n。然后是n个正整数。
Output
为每组測试数据输出它们的最小公倍数。每一个測试实例的输出占一行。
你能够如果最后的输出是一个32位的整数。
Sample Input
2 4 6 3 2 5 7
Sample Output
12 70
这道题对我的启示非常大。尽管是一道非常easy的题,但还是Wrong Answer了好几次。
#include<stdio.h> int GCD(long n,long m) { long i; if(n <m) { long t = n; n = m; m = t; } for(i = m;i >=1;i --) { if(n%i == 0&&m%i == 0) return i; } } int main(void) { int a,t,max,min; int n; while(scanf("%d",&n)!=EOF) { max = min = 1; a = max/min; while(n --) { scanf("%d",&t); min = GCD(a,t); max = a * t; a = max/min; } printf("%d\n",a); } }代码是这种。思路就是不断的两两求最小公倍数。可是认为会错非常疑惑。就去网上看了一些前辈的解答。发现他们都提到了公约数的位置的问题,即一定要先除公约数,否则假设先相乘的话会超出int的范围。
改进后:
#include<stdio.h> int GCD(long n,long m) //求最大公约数 { int i; if(n <m) { int t = n; n = m; m = t; } for(i = m;i >=1;i --) { if(n%i == 0&&m%i == 0) return i; } } int main(void) { int a,t,gcd; int n; while(scanf("%d",&n)!=EOF) { a = 1; while(n --) { scanf("%d",&t); gcd = GCD(a,t); a = a / gcd * t; //先除去公约数 } printf("%d\n",a); } }最后改进下求公约数的方法
#include<stdio.h> int GCD(long n,long m) //求最大公约数 { int i; if(n <m) { int t = n; n = m; m = t; } if(n % m == 0) return m; else return GCD(m,n%m); } int main(void) { int a,t,gcd; int n; while(scanf("%d",&n)!=EOF) { a = 1; while(n --) { scanf("%d",&t); gcd = GCD(a,t); a = a / gcd * t; } printf("%d\n",a); } }小结:出现错误,但肯定思路是对的,多从一些细节方面考虑。
HDU 2028 Lowest Common Multiple Plus
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。