首页 > 代码库 > 算法训练 最大最小公倍数
算法训练 最大最小公倍数
算法训练 最大最小公倍数
时间限制:1.0s 内存限制:256.0MB
问题描述
已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。
输入格式
输入一个正整数N。
输出格式
输出一个整数,表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定
1 <= N <= 106。
解题思路:其实看似挺简单的一道题,但是却需要分析一番。虽然知道是用贪心法,下面的代码能ac,但自己的贪心策略远远不够准确,不如最后面的方法简洁准确。自己的分析能力还是很烂。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #define for(i,x,n) for(int i=x;i<n;i++) #define ll long long int using namespace std; ll gcd(ll a,ll b){ ll t=a%b; while(b){ a=b; b=t; if(b==0){ return a; } t=a%b; } return a; } int main() { ll n; ll maxx=0; scanf("%lld",&n); if(n%2==1){ printf("%lld",n*(n-1)*(n-2)); return 0; }else{ ll t=n*(n-1)/gcd(n,n-1); for(i,n-40,n+1){ ll lcm=t*i/gcd(t,i); if(lcm>maxx){ maxx=lcm; } } t=(n-1)*(n-2)/gcd(n-1,n-2); t=t*(n-3)/gcd(t,n-3); if(t>maxx){ maxx=t; } printf("%lld",maxx); } return 0; }
下面是网上的代码,这是地址。
首先确定是从大到小开始看,然后考虑到第一个数是奇数时,奇偶奇,其中两个奇数中间差2,但奇数没有因子2。
第一个数是偶数时,n,n-1,n-2是 偶奇偶,这时候两个偶数之间一定会有公共因子2,然后需要n-2再往后推一个取n-3,即n,n-1,n-3(偶奇奇),但这时候要注意,n,n-3之间可能会有公共因子3,
这时候就需要判断n能否被3整除,如果可以,n-3也会被3整除,这样就不能取这三个数了,就不能再取n了,整体往后推一个,取n-1,n-2,n-3.
#include<iostream> using namespace std; int main() { long long n,ans; cin>>n; if(n<=2) ans=n; else if(n%2==1) ans=n*(n-1)*(n-2); else { if(n%3==0) ans=(n-1)*(n-2)*(n-3); else ans=n*(n-1)*(n-3); } cout<<ans<<endl; return 0; }
算法训练 最大最小公倍数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。