题解 CF235A 【LCM Challenge】

FCB_Yiyang2006✈ · 2020-03-28 12:07:50 · 题解

1.做这道题前需要掌握

(1) lcm 的一些基本性质

(2) lcm 的一些基本求法

(3) gcd 的一些基本性质

(4) 辗转相除

2.一个小引理

因为此题是求三个数 lcm, 所以珂以随意取三个数的 lcm 来考虑。

step1

不妨设三个数 a,b,c。

step2

令：

step3

先可考虑 a,b。

若：

则

进而推广至三个数：

(就直接连等了，各位巨佬珂以自己推一推)

所以我们得到结论

三个数的 lcm 的大小与 三数乘积 和 两两之间的 gcd 有关。

3.进入正题

题目描述清晰明了，不用多做解释。

思路

在 n 个数中满足

1.三个数乘积大

2.三个数两两的 gcd 尽可能小

分成两种情况：

1. n 为奇数

乘积最大的三个数：n, n-1, n-2。

在考虑这三个数的 gcd:

根据辗转相除性质:

又因为 n 为奇数

所以这三个数也两两互质。

那我们就当然输出 n*(n-1)*(n-3) 了！

2. n 为偶数(有点复杂)

我们还是可以考虑乘积最大的三个数：n, n-1, n-2。

但是此时就翻车了...

因为 n, n-2 都为偶数

所以 gcd(n,n-2)=2

输出时就是：n*(n-1)*(n-3)/2

因为这里出现除以2，n 较大时，lcm 较小，所以我们问：还有没有更大的结果呢？

我们可以把其中一个偶数换掉换成略小的一个

将 n-2 换为 n-3

这在 n 较大时且 n 不整除3时显然可以输出

再问：n 较大时，且 n 整除3时，有木有更大的结果？

当然是有的，我们还可以将 n 变为 n-1 就与奇数情况相同了。

输出：

当然，保险来说，n 为偶数的情况就上述的三种情况取一次MAX(因为 n 较小时有些玄学)

4.注意事项

1.n 小于3时会出现负数，单独考虑。

2.此题结果要开 longlong。

3.C++ 库中的 max 函数两个参数都是 int, 所以我们要手写 MAX 函数。

5.上代码

#include<bits/stdc++.h>
using namespace std;
long long n;//保险写法，类型转换不出错
long long Max(long long a,long long b)//手写Max
{
    if(a>b)
    {
        return a;
    }
    return b;
}
int main()
{
    scanf("%lld",&n);
    if(n==1)
    {
        printf("1");
        return 0;
    }
    if(n==2)
    {
        printf("2");
        return 0;
    }//特殊考虑
    if(n%2==1)
    {
        printf("%lld",n*(n-1)*(n-2));
    }//奇数情况
    else
    {
        if(n%3!=0)
        {
            printf("%lld",Max(n*(n-1)*(n-2)/2,n*(n-1)*(n-3)));
        }//偶数不整除3情况
        else
        {
            printf("%lld",Max(n*(n-1)*(n-2)/2,Max((n-1)*(n-2)*(n-3),n*(n-2)*(n-3)/3)));
        }//偶数整除3的情况
    }
    return 0;
}

(蒟蒻心地善良，可以直接 AC)

6.最后

感谢CF题库供题，洛谷管理员维护和翻译者的翻译

因为我比较弱，有些讲得不清楚的地方敬请谅解，可以在评论区提出。(不要忘了点赞鼓励哦)

祝各位早日 AC 本题！