程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 2028 Lowest Common Multiple Plus

HDU 2028 Lowest Common Multiple Plus

編輯:關於C++

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
這道題對我的啟發很大,雖然是一道很簡單的題,但還是Wrong Answer了好幾次。
#include

int GCD(long n,long m)
{
	long i;
	if(n =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
,a);
	}
}
代碼是這樣的。思路就是不斷的兩兩求最小公倍數,但是覺得會錯很疑惑,就去網上看了一些前輩的解答,發現他們都提到了公約數的位置的問題,即一定要先除公約數,否則如果先相乘的話會超出int的范圍。 改進後:
#include

int GCD(long n,long m)             //求最大公約數
{
	int i;
	if(n =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
,a);
	}
}
最後改進下求公約數的方法
#include

int GCD(long n,long m)             //求最大公約數
{
	int i;
	if(n 小結:出現錯誤,但肯定思路是對的,多從一些細節方面考慮。

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved