Hướng dẫn giải của Chữ số không (Đề chọn ĐTQG Phú Thọ 2015-2016)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đếm số chữ số 0 tận cùng liên tiếp (tính từ hàng đơn vị) của n! với 0 <= n <= 10^6. Đọc từ CAU1.INP, ghi ra CAU1.OUT.
Sub 1: Đếm thừa số 5 của từng số i — ~O(n log n)~
Số chữ số 0 tận cùng của n! bằng số thừa số 5 trong tích 12...*n, vì thừa số 2 luôn nhiều hơn. Duyệt i từ 1 đến n và đếm số lần i chia hết cho 5. Ví dụ n = 10 có 2 thừa số 5 (từ 5 và 10), kết quả 2.
Kết quả chấm: đạt 32/32 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) {
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
}
long long n;
cin >> n;
long long cnt = 0;
// Vet can: moi i trong 1..n, dem so thua so 5 trong i.
// So tan cung 0 cua n! bang so thua so 5 (so thua so 2 luon nhieu hon).
for (long long i = 1; i <= n; i++) {
long long t = i;
while (t % 5 == 0) {
cnt++;
t /= 5;
}
}
cout << cnt << endl;
return 0;
}
Sub 2: Công thức Legendre — ~O(log n)~
Số thừa số 5 của n! là n/5 + n/25 + n/125 + ... (chia nguyên). Không cần tính n! nên đủ nhanh.
Kết quả chấm: đạt 32/32 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) {
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
}
long long n;
cin >> n;
// Cong thuc Legendre: so tan cung 0 cua n! = n/5 + n/25 + n/125 + ...
long long cnt = 0;
for (long long p = 5; p <= n; p *= 5)
cnt += n / p;
cout << cnt << endl;
return 0;
}
Bình luận