蓝桥杯练习 _ALGO002_ 最大最小公倍数

问题描述

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

输入格式

 输入一个正整数 N。

输出格式

 输出一个整数，表示你找到的最小公倍数。

样例输入

 9

样例输出

 504

数据规模与约定

 1 <= N <= 106。

解答思路

首先要有一定的数学基础，要了解以下三个数学知识
 1、互质的三个数的最小公倍数为三数之积
 2、连续的两数互质
 3、连续的两奇数互质
根据提示使用贪心算法进行运算，可以分为三种情况
 1、输入的 n 为奇数。则由上面的知识可得，n 与 n-1 互质，n-1 与 n-2 互质，而由于 n 和 n-2 都为奇数，所以 n，n-1，n-2 三数互质，最小公倍数即为三者之积。
 2、输入的 n 为偶数，且 n 不为 3 的倍数。则由上面知识可知，n 与 n-1 互质，n 与 n-2 不互质，此时根据贪心策略，替换 n，n-1，n-2 之中较小的数 n-2 为 n-3，此时，n-1 与 n-3 互质，又因为 n 不是 3 的倍数，所以 n 与 n-3 互质。此时三数 n，n-1，n-3 互质，最小公倍数即为三者之积。
 3、输入的 n 为偶数，且 n 为 3 的倍数。此时，无法保证 n 与 n-3 互质，再次根据贪心算法替换 n-3 为 n-4，又发现 n 和 n-4 均为偶数，不互质，依次类推，替换最小值无法保证三数互质。根据贪心算法，替换第二小的值 n-1 为 n-2，发现 n-2 也为偶数，遇到了和上一步同样的问题，改变第二小的数同样无法做到三数互质。考虑修改最大值 n 为 n-1，此时，即为 1 中所述情况，n-1 为奇数。故 n-1，n-2，n-3 三数互质，最小公倍数即为三者之积。

代码实现

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        long n = input.nextInt();
        if(n<=2)
        {
            System.out.println(n);
        }
        if(n>2)
        {
            if(n%2!=0)
            {
                System.out.println((n)*(n-1)*(n-2));
            }
            else
            {
                if(n%3!=0)
                {
                    System.out.println(n*(n-1)*(n-3));
                }
                else
                {
                    System.out.println((n-1)*(n-2)*(n-3));
                }
            }
        }
    }

}