算法训练 最大最小公倍数

Posted on | In |

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

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

输出格式
输出一个整数，表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定
1 <= N <= 106。

按照常理来说，最大的应该是n, n-1, n-2这三个数，如果这三个数恰好互质，那再好不过。然而恰好当n为奇数时，这三个数互质。下面来解释下为什么。首先这三个数时连续的三个数。也就是n，n-1，n-2。因为n是奇数，所以奇偶奇不可能有2这个因数。那再看3，这三个连续的数最大相差的是2，然而我们知道如果n能被3整除那n+1，n+2（减去是一样的）就不能因为没加够一个3.同理如果n能被4整除那么n+1，n+2，n+3也都不能被4整除，因为没加够一个4.证毕。
  再看若n是偶数，那很自然的想到吧n-2往后挪一个变成奇数n-3就好了。但是这里有个问题，如果n刚好能被3整除的话那么n-3也能。那就还要除去一个3.不划算。那不能挪后面的就把前面的挪一下吧。变成n-1，n-2,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
#include<iostream>
#include<algorithm>
#define MAX 200+2
using namespace std;
int main(){
	long long n;
	long long  ans=0;
	cin>>n;
	if(n%2){
		ans=n*(n-1)*(n-2);
		
	}
	else if(n%3)
	{
		ans=n*(n-1)*(n-3);
		
	}
	else{
		
		ans=(n-1)*(n-2)*(n-3);
	}
	cout<<ans;
	}