首页 > 代码库 > 算法训练 最大最小公倍数

算法训练 最大最小公倍数

算法训练 最大最小公倍数  
时间限制: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;  
}   

 

算法训练 最大最小公倍数