首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。