51 nod 1419 最小公倍数挑战【数论/互质+思维】

1419 最小公倍数挑战

题目来源： CodeForces

基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题

 收藏

 关注

几天以前，我学习了最小公倍数。玩得挺久了，想换换口味。

我不想用太多的数字，我想从1到n中选三个数字（可以相同）。使得他们的最小公倍数最大。

Input

单组测试数据。
第一行有一个整数n (1≤n≤1,000,000)。

Output

输出一个整数表示选三个数字的最大的最小公倍数。

Input示例

9
7

Output示例

504
210

【分析】：相邻数互质，相邻奇数互质。

n为奇数的时候，由相邻数字一定互质和相邻奇数一定互质可知----->最优答案肯定是n*(n-1)*(n-2)。

n为偶数的时候，首先n和n-1是互质的，但n和n-2是不互质的，所以一个可以考虑的解是n*(n-1)*(n-3)。

那么n和n-3一定互质吗?不一定，当n%3==0的时候，最优解是(n-1)*(n-2)*(n-3)。

【代码】：

#include <bits/stdc++.h>

using namespace std;
#define LL long long
int main()
{
    LL n;
    while(cin>>n)
    {
        LL ans;
        if(n==1)
        {
            cout<<1<<endl;
            continue;
        }
        
        if(n==2)
        {
            cout<<2<<endl;
            continue;
        }
        
        if(n%2==0)
        {

            if(n%3==0)
            {
                ans=(n-1)*(n-2)*(n-3);
                cout<<ans<<endl;
            }

            else
            {
                ans=n*(n-1)*(n-3);
                cout<<ans<<endl;
            }
        }
        else
        {
            ans=n*(n-1)*(n-2);
            cout<<ans<<endl;
        }
    }
    return 0;
}