MUMAX - Số mũ lớn nhất

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 0.005s
Giới hạn bộ nhớ: 256M
Tác giả:
siro
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Cho ~N~ là một số nguyên dương lớn hơn ~2~. Xét tích ~T = 1 × 2 × 3 × ... × N~.

Yêu cầu: Trong các ước có dạng ~2^k (k ∈ N)~ của số ~T~, hãy tìm ~k~ lớn nhất.

Input

  • Số nguyên dương ~N (1 \le N \le 10^8)~

Output

  • Số ~k~ lớn nhất tìm được.

Sample

Input #1
6
Output #1
4

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 2
    dinhvantung0611  đã bình luận lúc 11, Tháng 1, 2024, 7:26 ← sửa 3

    Ý tưởng: Mình sẽ lấy ví dụ n = 16 để các bạn có ý tưởng (còn các bạn code đi nhé :>)

    16! = 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 (*)

    16! = 2 * 3 * (2 * 2) * 5 * (2 * 3) * 7 * (2 * 4) * 9 * (2 * 5) * 11 * (2 * 6) * 13 * (2 * 7) * 15 * (2 * 8)

    Bây giờ ta sẽ đếm số lượng số 2 để tìm k vì 2^k = số lượng số 2 mà (bỏ mấy số lẻ đi): k = 0

    2, (2 * 2), (2 * 3), (2 * 4), (2 * 5), (2 * 6), (2 * 7), (2 * 8) (Thấy ngay số lượng số 2 ở đây = số lượng số chẵn từ [1, 16], nên ta lấy 16 / 2 ra số lượng số chẵn) => k += (16 / 2) (+= 8)

    Ta chia dãy trên cho 2 ta được: 1, 2, 3, 4, 5, 6, 7, 8

    Lấy k + số các số chẵn [1, 8] => k += (8 / 2) (+= 4)

    Ta chia dãy trên cho 2 ta được: 1, 2, 3, 4

    Lấy k + số các số chẵn [1, 4] => k += (4 / 2) (+= 2)

    Ta chia dãy trên cho 2 ta được: 1, 2

    Lấy k + số các số chẵn [1, 2] => k += (2 / 2) (+= 1)

    => k = 8 + 4 + 2 + 1 = 15, là số lượng số 2 nằm trong biểu thức (*) trên.


    • 0
      dinhvantung0611  đã bình luận lúc 2, Tháng 3, 2024, 7:16 ← sửa 2

      Có thể bạn hiểu ý tưởng, tuy nhiên chưa AC. Code mình cũng vậy (C++), lúc nộp AC với time chạy là 0.002s, có lúc lại TLE > 0.005s. Cái này mình nghĩ do trình chấm đôi lúc bị "khờ" do time limit quá chặt (lệch vài mini giây). Còn cách làm mình nghĩ là khá tối ưu rồi


      • 2
        ______  đã bình luận lúc 9, Tháng 3, 2024, 7:41

        mãi iu bn nhìu

        include <iostream>

        using namespace std; int main() { int N; cin >> N;

        int k = 0;
int a = 2;
while (a <= N) {
    k += N / a;
    a *= 2;
}

cout << k << endl;

return 0;

        }


  • 0
    vanhhn  đã bình luận lúc 26, Tháng 9, 2023, 13:00

    bài này time chặt quá