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ả:
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
:) tôi làm full test bạn chỉ cần đếm tổng số số chia hết cho 2^i (<n, các số này được lập lại ở mỗi lần lên mũ là được) dùng log2(n) tìm i r dùng for chạy count += (n - n % (long long) pow(2, i) - pow(2, i)) / pow(2,i) + 1;
Ý 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.
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
bài này time chặt quá