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

這道題對我的啟發很大，雖然是一道很簡單的題，但還是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 小結：出現錯誤，但肯定思路是對的，多從一些細節方面考慮。