ALGO-2 试题算法训练最大最小公倍数

本文主要是介绍ALGO-2 试题算法训练最大最小公倍数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：ALGO-2 试题算法训练最大最小公倍数

题目描述

资源限制
时间限制：1.0s 内存限制：256.0MB

问题描述
已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。

输入格式
输入一个正整数N。

输出格式
输出一个整数，表示你找到的最小公倍数。

样例输入
9

样例输出
504

数据规模与约定
1 <= N <= 10^6。

解题思路

一开始看完题目之后，我想那不就是把最大的三个数相乘然后输出就好了？于是我就直接输出n*(n-1)*(n-2)，最终得分10分。

好吧，竟然还混到了10分，思路就是错的。再仔细看题，想着想着这不是要输出最大的三个互质的数吗？于是我从n开始循环，每次判断n和n-1还有n-2是否互质，互质的话就输出。本以为可以过了，结果50分。

最后实在是想不明白为什么，就上网搜博客，发现我的思路是对的，但是代码实现有问题。

比如输入95152，按照我的判断应该输出95151 95150 95149三个数的乘积，我就想也没问题啊，看了别人的博客后发现，这三个数确实是互质的，但不是最大的，把95150改为95152就会是最大的，并且三个数还是互质。

程序代码

#include<iostream>
#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long n; 
long long a,b,c;
/*int gcd(long long aa,long long  bb) {int temp;while(bb) {temp=aa%bb;aa=bb;bb=temp;}return aa;
}*/
int gcd(long long aa,long long bb) {return bb==0?aa:gcd(bb,aa % bb);
}
int main() {scanf("%d",&n);/*for(int i=n;i>=3;--i) {//这一坨是一开始50分的做法a=i;b=i-1;c=i-2;int e=gcd(a,b);int f=gcd(a,c);int d=gcd(b,c);if(d==1&&e==1&&f==1) {printf("%lld",a*b*c);return 0;}} *///下面这个是100分做法if(n <= 2) return n;// 1.如果n是一个奇数， 那么它的最大值： n * (n - 1) * (n - 2)// 例：n = 9, max = 9 * 8 * 7else if(n % 2 == 1) {long long c=n * (n - 1) *( n - 2);printf("%lld",c);}else {// 2.当n是一个偶数时，讨论它能否被3整除// 3.如同时能被 2 和 3 整除， 则其最大值：(n - 1) * (n - 2) * (n - 3)// 例：n = 12, max = 11 * 10 * 9if(n % 3 == 0) {long long c=(n - 1) * (n - 2) * (n - 3) ;printf("%lld",c);}// 4.如只能被 2 整除， 则其最大值为：n * (n - 1) * (n - 3)// 例：n = 16, max = 16 * 15 * 13else {long long c=n * (n - 1) * (n - 3);printf("%lld",c);}}return 0;
}