28-算法训练 最大最小公倍数 -贪心

时间:2021-11-01 13:11:43
                算法训练 最大最小公倍数  
时间限制:1.0s   内存限制:256.0MB
       
问题描述

已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。

输入格式

输入一个正整数N。

输出格式
输出一个整数,表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定

1 <= N <= 106。

注意:

1.数据大,int 会超过范围;

2.推导过程:

n 为奇数时, 毫无疑问 n * (n - 1) * (n - 3) 最大,且是最小公倍数,应为两两之间没有公约数,因为相邻的n, n -1 只差为1,肯定不能,而 n, n - 2 之间差 2 但都是奇数,有都不能被2整除,故,三者之积为最小公倍数;

n 为偶数时:

n * (n - 1) * (n - 3)  这样应该是最大的,但是无法保证 n, n - 3 之间不能被3整除,如,9,10, 11, 12, 故此时就得用下面的式子最大了;

(n - 1) * (n - 2) * (n - 3), 这样(n-1)为奇数,如第一种情况了,所以一定三者没有大于1的公约数。

另外: 当 n = 1, n = 2时公式不适用了!!!要特判。

import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		long n;
		n = cin.nextLong();
		if(n == 1) {
			System.out.println(1);
		}
		else if(n == 2) {
			System.out.println(2);
		}
		else {
			if(n % 2 == 0) {
//				System.out.println(Math.max(n * (n - 1) * (n - 3), (n - 1) * (n - 2) * (n - 3)) );
				//n 和 n - 3 之间可以会被3整除,如9,10,11,12
				if(n % 3 == 0) {
					System.out.println((n - 1) * (n - 2) * (n - 3));
				}
				else {
					System.out.println(n * (n - 1) * (n - 3));
				}
			}
			else {
				System.out.println(n * (n - 1) * (n - 2));
			}
		}
	}
}