Lowest Common Multiple Plus

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 30977 Accepted Submission(s): 12566


Problem Description 求n個數的最小公倍數。
Input 輸入包含多個測試實例，每個測試實例的開始是一個正整數n，然後是n個正整數。
Output 為每組測試數據輸出它們的最小公倍數，每個測試實例的輸出占一行。你可以假設最後的輸出是一個32位的整數。
Sample Input

2 4 6
3 2 5 7

Sample Output

12
70

分析：兩個數的最小公倍數 lcm( x , y ) = x * y / gcd( x , y )。其中 gcd() 是這兩個數的最大公約數，可以采用“輾轉相除法”求解。所以這題的關鍵是求最大公約數。

import java.util.Scanner;

public class Main {

	// 最大公約數
	static long gcd(long a, long b) {
		long remainder = a % b;
		while (remainder != 0) {
			a = b;
			b = remainder;
			remainder = a % b;
		}
		return b;
	}

	// 最小公倍數
	static long lcm(long a, long b) {
		return a * b / gcd(a, b);
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		while (scanner.hasNext()) {
			int n = scanner.nextInt();

			long temp = 1;
			for (long i = 0; i < n; i++) {
				long num = scanner.nextLong();
				temp = lcm(temp, num);
			}

			System.out.println(temp);
		}
	}
}