最小公倍数

Posted on In

题目大意：给定 𝑛 ，你需要找到三个 [1,𝑛] 中的正整数，使得它们的最小公倍数最大

考虑n的奇偶情况

n如果为奇数，那么显然当前\(n,(n-1),(n-2)\)互质，我们直接乘起来他们三个就好

n如果为偶数，那么显然\(n,(n-2)\)存在公约数2，我们就考虑往后面挪一个，换成\(n-3\)

但是如果n本身就是三的倍数怎么办？

那么我们就把n变成\(n-1\)(奇数)这样\((n-1)\times (n-2)\times (n-3)\)就是最优解了

那就不如

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 66;

int n, res;

inline int gcd(int x, int y)
{
    return ! y ? x : gcd(y, x % y);
}

inline int lcm(int x, int y)
{
    return x * y / gcd(x, y);
}

inline int maxs(int x, int y)
{
    return x > y ? x : y;
}

signed main()
{

    int i, x;
    n = read();

    if (n & 1) put(n * (n - 1) * (n - 2));
    else 
    {
        if (! (n % 3)) put((n - 1) * (n - 2) * (n - 3));
        else put(n * (n - 1) * (n - 3));
    }

    fclose(stdin), fclose(stdout);
    return 0;
}