已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。
输入格式输入一个正整数N。
输出格式输出一个整数，表示你找到的最小公倍数。样例输入9样例输出504数据规模与约定1 <= N <= 106。
思路:这个题其实还真应该好好想想,刚开始就很想当然的认为找了三个最大的数相乘,没考虑要分奇偶情况讨论静下心来一想其实还真是这么回事:对于奇数的话我们挑选出最大的三个数：奇偶奇 n n-1 n-2 两个奇数，虽然变化了2但是都是奇数,没有公因子2，所以此时他们是最大的最小公倍数.对于偶数如果我们还是挑选出三个最大的数的话：偶奇偶 n n-1 n-2 两个偶数肯定会有一个公因子2,此时就不会满足最大,为了还是能满足两个奇数一个偶数 我们选择 n n-1 n-3 即减少一个,但是新的问题又来了 n和 n-3 可能会包含一个新的公因子3 （因为他们之间变化了3，或者相差3 不会再出现更大的公因子了）如果包含了的话会使这个最大最小公倍数更小,所以需要特判一下,如果n和n-3有公因子3 那么我们就只能将n减少 选择 n-1 n-2 n-3 三个连续的最大数 奇偶奇 就满足了n为奇数的情况的最大;#include<bits/stdc++.h>using namespace std;long long n;int main(){ scanf("%lld",&n); if(n<=2) { PRintf("%lld/n",n); } else if(n%2==1) printf("%lld/n",n*(n-1)*(n-2)); else { if(n%3) printf("%lld/n",n*(n-1)*(n-3)); else printf("%lld/n",(n-1)*(n-2)*(n-3)); } return 0;}
新闻热点
疑难解答
