【蓝桥】试题 算法训练 最大最小公倍数

　　1 <= N <= 10^6。

————————————————————————————————————————————

思路

　　需要求三个数最小倍数的最大值，则这三个数需要尽量的大。从样例可以看出答案504=7*8*9，即答案就是N*(N-1)*(N-2)。这个结果的前提是N，N-1，N-2是两两互质的。

（1）我们可以知道任何两个相邻的数是互质的，而且相邻的两个奇数也是互质的，所以当N是奇数时，N，N-1，N-2两两互质。则答案是N*(N-1)*(N-2)。

（2）当N是偶数时，N和(N-1)互质，(N-1)和(N-2)互质，但是N和(N-2)有公因数2，不是互质的。此时我们依据贪心原则，将最小的数减小（选择最小的数减小会使结果减小的幅度最小），将第三个数从(N-2)减小到(N-3)，即N*(N-1)*(N-3)。N和(N-1)互质，(N-1)和(N-3)是相邻奇数，所以也互质，我们只需要关注N和(N-3)是否互质。当N是3的倍数时，可知N和(N-3)有公因数3，所以不互质，这种情况我们稍后讨论；当N不是3的倍数时，N和(N-3)是互质的，所以答案是N*(N-1)*(N-3)。

（3）经过上面的讨论我们还剩一种情况，即N是偶且N是3的倍数时。我们发现N*(N-1)*(N-3)是不可以的，因为N和N-3不互质，可知这个结果不是最大的。我们继续减小第三个数，得到N*(N-1)*(N-4)，可见N和(N-4)都是偶数，不互质。继续减小第三个数得到N*(N-1)*(N-5)，我们不能明显的看出有两个数不互质，我们就假设这个组合可以。前面说到减少第三个数造成结果的减小最少，但是第三个数已经减小到了一定程度，我们不妨考虑(N-1)*(N-2)*(N-3)，这就是（1）中的情况了。我们比较(N-1)*(N-2)*(N-3)和N*(N-1)*(N-5)，发现在N>时，(N-1)*(N-2)*(N-3)更大，这就是最后答案。

代码

#include <iostream>
#include <vector>
using namespace std;
vector<int> v;

int main()
{
    long long int ans,N;
    cin >> N;
    if(N<=2)
        ans=N;
    else if (N % 2 != 0)
    {
        ans = N * (N - 1) * (N - 2);
    }
    else
    {
        if (N % 3 == 0)
        {
            ans = (N - 1) * (N - 2) * (N - 3);
        }
        else
        {
            ans = N * (N - 1) * (N - 3);
        }
    }
    cout << ans << endl;
    return 0;
}