首页 > 代码库 > hrbust1632 最大的最小公倍数(欧几里得)

hrbust1632 最大的最小公倍数(欧几里得)

本文出自:http://blog.csdn.net/svitter

原题:http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1632


题意:给你一个数字N,让你在1~n中选三个数字,使其最小公倍数最大。


题解:水题一发。。半天没A。。呵呵呵呵。

1。相邻自然数肯定互质。

2。依据辗转相除法。。shit- -。。n和n-3如果有最大公约数肯定是3。


AC:

//============================================================================
// Name        : num.cpp
// Author      : vit
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define lln long long int

int main() {
	lln n;
	lln ta, tb;
	while(~scanf("%lld", &n))
	{
		if(n <= 2)
			printf("%lld\n", n);
		else
		{
			if(n & 1)
				printf("%lld\n", n*(n-1)*(n-2));
			else
			{
				if(n % 3 != 0) ta =n*(n-1)*(n-3);
				else ta = 0;
				tb = (n-1)*(n-2)*(n-3);
				printf("%lld\n", ta > tb ? ta : tb);
			}
		}
	}
	return 0;
}