蓝桥杯 算法训练 最大最小公倍数

问题描述

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

输入格式

输入一个正整数N。

输出格式

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

样例输入

9

样例输出

504

数据规模与约定

1 <= N <= 106。

思路：三个数两两互为质数

1.当n为奇数时，不难想到n，n-1，n-2三个数两两互为质数，乘积最大，也是三个数的最小公倍数。所以有最大最小公倍数为：n*(n-1)*(n-2)。

2.当n为偶数时，n和n-2有公约数2，所以n-2不能采用；继续找下一个较大的数n-3。这时可看出n，n-1，n-3两两互质；

但是当偶数n也能让被3整除时，会发现n-3与n会有公约数3，这时如果再向下找最大数，会发现n-4与n有公约数2，不适合，所以舍弃n，选用n-1，n-2，n-3三个数，类似于第一种情况，两两互质。

所以n为偶数时：

1）n不被3整除：n*（n-1）*（n-3）；

2）n能被3整除：（n-1）*（n-2）（n-3）。

#include<cstdio>
using namespace std;
int main()
{
    long long n;
    scanf("%lld",&n);
    if(n%2==1)
        printf("%lld\n",n*(n-1)*(n-2));
    else if(n%2==0)
    {
        if(n%3==0)
            printf("%lld\n",(n-1)*(n-2)*(n-3));
        else
            printf("%lld\n",n*(n-1)*(n-3));
    }
    return 0;
}