蓝桥杯-算法训练 最大最小公倍数

前言

记录一下自己刚入门算法时所遇到的一些"无从下手"题

题目

问题描述

已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。
输入格式
	输入一个正整数N。
输出格式
	输出一个整数，表示你找到的最小公倍数。
样例输入
	9
样例输出
	504
数据规模与约定
1 <= N <= 106。

解析

三个数互质时最小的公倍数最大
根据数论知识：任意大于1的两个相邻的自然数都是互质的.

1.奇数-偶数-奇数
易知，三个连续的数若为此情况，三个都是互质的，则此时最大的最小公倍数即为n*(n-1)*(n-2);

2.偶数-奇数-偶数，此时因为存在两个偶数，二者存在公因数2，最小公倍数会除以2，这样不能保证最大（由于后面的方法只需将数前后移动1-2位，因此除以2的方法明显会大幅减小最小公倍数），因此可以先将后面的偶数减1，得n-3,
此时需要考虑n是否为3的倍数，因为若为3的倍数，明显会与n-3有公因数3，最大的最小公倍数为(n-1)(n-2)(n-3)，所以n若不为3的倍数，最大的最小公倍数则为n*(n-1)*(n-3),

推荐解析:蓝桥杯 - 算法训练 - ALGO-2 最大最小公倍数

代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int main(){
	long long int n,ans;
	scanf("%I64d",&n);
	if(n<3)ans=n;
	else{
		if(n%2!=0)ans=n*(n-1)*(n-2);
		else if(n%3!=0)ans=n*(n-1)*(n-3);
		else ans=(n-1)*(n-2)*(n-3);
	}
	printf("%I64d",ans);
	return 0;	
} 

后记

红雨瓢泼泛起了回忆怎么潜
你美目如当年
流转我心间
渡口边最后一面
洒下了句点
与你若只如初见
何须感伤离别