Tìm số chữ số 0 cuối của N! khi biểu diễn trong cơ số 16 (hexadecimal). Ví dụ:
Input: N = 7 → Output: 1 Giải thích: 7! = 5040 = 13B0 (cơ số 16) có 1 số 0 cuối. Input: N = 11 → Output: 2 Giải thích: 11! = 39916800 = 2611500 (cơ số 16) có 2 số 0 cuối.
Vì 16 = 2⁴, số chữ số 0 cuối bằng số mũ của 2 trong N! chia 4 (lấy phần nguyên).
Phương pháp giải
Áp dụng công thức Legendre cho số nguyên tố 2: count = N/2 + N/4 + N/8 + ... Kết quả = count / 4.
Ví dụ minh họa
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 11;
long long count = 0;
long long power = 2;
do {
long long value = n / power;
count += value;
power *= 2;
} while (value != 0);
long long result = count / 4;
cout << "Số chữ số 0 cuối trong cơ số 16: " << result;
return 0;
}
Kết quả
Số chữ số 0 cuối trong cơ số 16: 2
Giải thích
- Khởi tạo power = 2 để tính số mũ của 2.
- Vòng lặp Legendre: cộng dồn N/power, nhân power thêm 2 mỗi lần.
- Chia count cho 4 vì 16 = 2⁴.
Kết luận
Đã giải bài toán trailing zeros cơ số 16 bằng Legendre. Code C++ áp dụng cho Java, C, Python. Hy vọng hữu ích.