CF235A

2simon2008 · 2021-01-05 16:37:27 · 个人记录

题意

给你一个数 n ，求小于等于n的三个数的最小公倍数最大值是多少。

思路

话说这是一道贪心题目，所以贪心的方法很重要。 重点是数学推导，贪心的意味主要在推导过程中，不在代码中。

n 为奇数

那很简单，由于 n , n-1 , n-2互质，于是答案就是 n(n-1)(n-2)——算式 1 。

n 为偶数

这里要分类讨论了。

按照奇数的分析，尽量两数之间互质，于是就是n(n-1)(n-3)（n 与 n-2 不互质）。——算式 2

如果n、n-3最大公因数为 3 ，那么知道n(n-1)(n-3)再除以 3 （有公倍数 3 ，要除掉）是没有 (n-1)(n-2)(n-3) 或者 n(n-1)(n-5)（前提是 n比 5 大 ）大的。

此时，由于(n-2)(n-3) 比 n(n-5) 大 6，因此(n-1)(n-2)(n-3)较大：——算式 3 。

调试过程

辛酸的……

注意 if (n mod 3) 指 n 不整除 3 ，由于忘打 ==0了，于是错了。

代码

#include<bits/stdc++.h>
using namespace std;
long long n;
int main()
{
    cin>>n;
    if(n<3){
        cout<<n<<endl;
        return 0;
    } //注意特判
    if(n%2){
        printf("%lld\n",n*(n-1)*(n-2));
        return 0;
    }//奇数时，用算式1
    if(n%3==0){
        printf("%lld\n",(n-1)*(n-2)*(n-3));
        return 0;
    }
        //n与n-3不互质，有最大公约数为3，用算式3
    printf("%lld\n",n*(n-1)*(n-3));
        //n与n-1与n-3都互质，用算式2
    return 0;
} 

完结撒花！