算法练习-蓝桥杯练习系统-算法训练-ALGO-2 最大最小公倍数（※包括最大公约数、最小公倍数的总结）

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。
输入格式
输入一个正整数N。
输出格式
输出一个整数，表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定
1 <= N <= 106。

一开始以为这题的重点在，怎么求三个数的最小公倍数（LCM），然后去复习了一遍求最小公倍数的几种方法，也算是一个容易忘记的总结，将它放在本文结尾。后面发现用穷举法去找三个数的组合效率太低了。

这个时候才转变思路，往乘积大的那个方面去想，但是无奈数学基础不好，没有思考到互质那一层，后面找到了一篇回答，才恍然大悟，回答链接在此，作者：阿拉伯字母二世。

涉及到的数学常识，应该是小学数学吧，我太菜了

两个数的最小公倍数一定小于等于其乘积；而当这两个数互质时（如果组成分数无法约分时），其最小公倍数最大，等于其乘积。
两个相邻的数，一定互质。也就是：最大公约数=1，最小公倍数=其乘积。
相邻的两个奇数也一定互质。
推广到多个数，使其两两互质，这时：最大公约数=1，最小公倍数=多个数乘积。
差为3的两个数不互质！！！（例如9和6）
为什么要加上最后这一条呢？ 很像是一句废话，但是容易犯错。因为如果N是偶数，在找最大的三个两两互质的数的时候，因为N和N-2都是偶数，并不互质，这样就会找到N，N-1，N-3这个组合，所以这条是差为3的两个数不互质，而不是差为2的两个数不互质，也不是差为5的两个数不互质（当然如果题目改成任选五个数进行组合，那就可以加上这一条了）

掌握以上质数有关性质，就能解出这道题了。
思路找对后，很简单。

#include <iostream>using namespace std;int main(){long long n = 0;cin>>n;long long res = 0;if(n==1) cout<<\"1\";else if(n<=2) cout<<\"2\";else if(n<=3) cout<<\"6\";else if(n%2==1){res = n*(n-1)*(n-2);}else{if(n%3==0){res =(n-1)*(n-2)*(n-3);}else{res =n*(n-1)*(n-3);}}cout<<res;return 0;}

还有一个在代码中需要注意的，就是n和答案的数据类型，必须是

long long

类型，测试数据第一个就是n=95125，ans=861460772824848

每个long long类型的变量占8字节,64位
其表示范围为-9223372036854775808 ~ 9223372036854775807。-263 ~ 263-1
大概1019
long long 类型输出的时候,printf函数,用
%lld
格式输出

以后看到类似题目，记得质数有关这些性质！！！！！！！！！！！！！！！！！

最小公倍数、最大公约数

最大公约数

手头有纸有笔，最好用的是短除法。两个数一起除，直到互质，最后把所有的除数相乘。

除此之外，纸笔可以算的还有：

辗转相除法

/*辗转相除法基本思想：被除数 / 除数 =商...余数将每次除得余数作第二次的除数，除数作第二次的被除数，直到余数为0，本次除数（上一次余数）即为最大公约数。*/int min_ab = 0;while(1){cout<<a<<\"/\"<<b<<\"=\"<<a/b<<\"...\"<<a%b<<endl;min_ab = a%b;int temp = b;b = a%b;a = temp;if(a%b==0) break;}

辗转相减法

/*辗转相除法基本思想：A-B=C，包含差的ABC三个数中选取最小的两个相减，直到取得的两数相等，即下一次相减等于0，相等的数即为最大公约数。*/while (m != n){while (m>n) { m = m - n; }while (n>m) { n = n - m; }}

辗转相除和辗转相减计算机也可以用，多个数可以用递归，只需要将前两个数得到的最大公约数和第三个再求最大公约数即可。

最小公倍数

公式法：（已知最大公约数，或者最大公约数好求）
性质：两数乘积 = 两数的最大公约数 * 两数的最小公倍数
所以在已知最小公约数的情况下，用乘积除以最大公约数得最小公倍数。

不知道最大公约数的情况下：

短除法（将除得所有外侧结果相乘）
分解质因数
先把这几个数的质因数分解写出来，最小公倍数等于它们所有的质因数的乘积（如果有几个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数）。
举例：求27和15的最小公倍数
27 = 3 * 3 * 3
15 = 3 * 5
按照规则是3*5，但是3是两个数分解得到相同的质因数，这个时候选择质因数个数较多的成为它的次数。较多的次数是3，即33 * 5 = 135，最大公倍数为135。