WUSTOJ 1304: 最大最小公倍數（Java）

題目連結：1304: 最大最小公倍數

Description

已知一個正整數 N N N，問從 1 ∼ N 1 \sim N 1∼N中任選出三個數，他們的最小公倍數最大可以為多少。

Input

輸入一個正整數 N N N。 3 ⩽ N ⩽ 1 0 6 3 \leqslant N \leqslant 10^6 3⩽N⩽106

Output

輸出一個整數，表示你找到的最小公倍數。

Sample Input

Sample Output

分析💬

1 ∼ n 1 \sim n 1∼n中最大的三個互質的數的乘積就是結果。

這裡要用到2個結論（證明）：

1. 任意兩個相鄰的正整數互質
2. 任意兩個相鄰的正奇數互質

是以

1. 當 n n n為奇數時， a n s = n ∗ ( n − 1 ) ∗ ( n − 2 ) ans=n*(n-1)*(n-2) ans=n∗(n−1)∗(n−2)，這三個數兩兩互質

2. 當 n n n為偶數時， n ， n − 1 ， n − 2 n，n-1，n-2 n，n−1，n−2三個數中的 n n n和 n − 2 n-2 n−2都是偶數，不互質，是以需要将其中一個數變為奇數。

   若将最小的 n − 2 n-2 n−2變為 n − 3 n-3 n−3，那麼 n n n和 n − 3 n-3 n−3有可能都是 3 3 3的倍數，那就不互質了，是以需要判斷 n n n是否是 3 3 3的倍數。

   若 n n n是 3 3 3的倍數，就将 n n n變為 n − 3 n-3 n−3，則 a n s = ( n − 1 ) ∗ ( n − 2 ) ∗ ( n − 3 ) ans=(n-1)*(n-2)*(n-3) ans=(n−1)∗(n−2)∗(n−3)，

   若不是 3 3 3的倍數，就将 n − 2 n-2 n−2變為 n − 3 n-3 n−3，則 a n s = n ∗ ( n − 1 ) ∗ ( n − 3 ) ans=n*(n-1)*(n-3) ans=n∗(n−1)∗(n−3)。

代碼💻

/**
 * Time 224ms
 * @author wowpH
 * @version 1.1
 * @date 2019年6月9日下午10:51:26
 * Environment:	Windows 10
 * IDE Version:	Eclipse 2019-3
 * JDK Version:	JDK1.8.0_112
 */

import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(new InputStreamReader(System.in));
		long n, ans;
		while (sc.hasNext()) {
			n = sc.nextInt();
			if (1 == (n % 2)) {// n是奇數
				ans = n * (n - 1) * (n - 2);
			} else if (0 == (n % 3)) {// n是偶數且是3的倍數
				ans = (n - 1) * (n - 2) * (n - 3);
			} else {// n是偶數但不是3的倍數
				ans = n * (n - 1) * (n - 3);
			}
			System.out.println(ans);
		}
		sc.close();
	}
}
           

結論：任意兩個相鄰的正整數互質

證：設兩個正整數分别為n，n+1
    假設它們不互質，那麼存在一個公約數a(a>1)，使得n%a=0和(n+1)%a=0成立。
    因為n%a=0成立，于是(n+1)%a=1成立，與假設相沖突。
    故假設不成立，原結論成立。
           

結論：任意兩個相鄰的正奇數互質

證：設兩個正奇數為n，n+2
	假設它們不互質，那麼存在一個公約數a(a>1)，使得n%a=0和(n+2)%a=0成立
	因為n%a=0，是以(n+2)%a=2成立
	要想與假設不沖突，那麼a必須為2，于是n為偶數，與題意相沖突。
	故假設不成立，原結論成立
           

版權聲明：

1. 轉載請于首頁注明連結形式的WUSTOJ 1304: 最大最小公倍數（Java）——wowpH；
2. 代碼原創，公開引用不能删除首行注釋（作者，版本号，時間等資訊）；
3. 如果有疑問歡迎評論區留言，盡量解答；
4. 如果有錯誤，還望大俠評論區指正。