Bội chung

Points: 2

Time limit: 1.0s

Memory limit: 98M

Author:

Giang_CNTT3_K60

Problem type

Bội chung nhỏ nhất của 3 số nguyên dương là số nguyên dương nhỏ nhất mà chia hết cho cả ba số đó.

Gọi X bội chung nhỏ nhất của 3 số nguyên bất kì không lớn hơn số n cho trước. Hãy tìm MAX(X)

Input

Số nguyên dương n \((2 < n \le 10^6)\)

OutPut

MAX(i, j, k) (1 <= i < j < k <= n)

Ví dụ

Input

Output

Giải thích

LCM(9, 8, 7) = 9*8*7 = 504

Comments

3
NgocAnh_CNTT3_K61 commented on Oct. 24, 2021, 11:08 a.m.
Mình có 1 sol khác khá thú vị muốn đóng góp đến mọi người. À tất nhiên sol này không phải do mình nghĩ ra đâu :D

Với n lẻ, ta có ans = n(n-1)(n-2)

Với n chẵn, ta sẽ có 2 trường hợp:

Nếu n chia hết cho 3, ans = (n-1)(n-2)(n-3)

Nếu n không chia hết cho 3, ans = n(n-1)(n-3)

TICHPX commented on Oct. 24, 2021, 3:08 a.m. ← edited →

Code tham khảo

#include<bits/stdc++.h>
using namespace std;

long long bc(long long a,long long b,long long c)
{
    if(c<=0) return 0;
    long long z=__gcd(a,b);
    a=a/z*b;
    z=__gcd(a,c); 
    return a/z*c;
}
int main()
{
    long long n,res=0,t;
    cin>>n;
    for(int i=n;i>=n-5 && i>2;i--)
    for(int j=i-1;j>=n-6 && j>1;j--)
    for(int k=j-1;k>=n-7 && k>0;k--)
    {
        t=bc(i,j,k);
        if(res<t) res=t;
    }
    cout<<res;
}

0

sy_it5_k61 commented on Oct. 24, 2021, 9:30 a.m.

sao lại chỉ kiểm tra đến -5 mà không phải hơn thầy nhỉ