Bội chung

Submit solution
Points: 2
Time limit: 1.0s
Memory limit: 98M
Author:
Giang_CNTT3_K60
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

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

9

Output

504

Giải thích

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

Comments


  • 6
    shioiori  commented on Oct. 24, 2021, 3:08 p.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)

  • 0
    TICHPX  commented on Oct. 24, 2021, 7: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
      sguenm  commented on Oct. 24, 2021, 1:30 p.m.

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