CF235A题解

EatBread · 2021-07-01 22:11:21 · 个人记录

这道题我用了几个判断语句，就 AC 了。

思路

首先要判断 n 是否是 1 或 2，如果是则直接输出原数。

除去 1 和 2 本题其实就只有两种情况。

n 为奇数：

直接输出 (n-1)*n*(n-2)，因为如果 n 为奇数，

那么 \gcd(n-1,n,n-2)=1，因为任何一个奇数（1 除外）都不可能跟它加 2 有公约数（1 除外），

而相邻的两个数更是（1 除外）没可能，所以得出结论。

n 为偶数：

如果 n 为偶数，那么 \gcd(n-2,n)=2，

因此不能用 n-2，所以相比之下更大应该输出 (n-1)*n*(n-3)，

但假如 n 是 3 的倍数就不行了，因为 \gcd(n-3,n)=3，所以如果 n 是 3 的倍数，就输出 (n-1)*(n-3)(n-2)，

因为由于 n-2 不能用，n-3 也不能用，所以只能输出 (n)*(n-4)(n-5)，相比之下，还不如输出 (n-1)*(n-3)(n-2)。

注意要特判 n 为一或二的情况。

程序

#include<bits/stdc++.h>
using namespace std;
long long n;
int main()
{
     cin>>n;
     if(n==1){cout<<1;return 0;}
     if(n==2){cout<<2;return 0;}
     if(n%2==1)cout<<(n-1)*n*(n-2);
     if(n%2==0){
     if(n%3==0)cout<<(n-1)*(n-3)*(n-2);
     else cout<<(n-1)*n*(n-3);}
    return 0;
}