Bội chung


Submit solution

Points: 2
Time limit: 1.0s
Memory limit: 98M

Author:
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

9

Output

504

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)

  • 0
    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ỉ