Hướng dẫn giải của Đếm số 0
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.
Ý tưởng làm bài:
- Trước tiên ta có giai thừa của một số là tích các số từ 1 tới số đó (đặc biệt có giai thừa của 0 là 1)
- Ta nhận thấy rằng, để có số 0 ở cuối của một số, thì nó nó phải có tích của 2 và 5. (Khi phân tích một số ra tích các thừa số nguyên tố: ví dụ: 9=3mũ2, 10=2mũ1 nhân 5mũ1, 18=2mũ1 nhân 3mũ 2, 100=2mũ2 nhân 5mũ2), nói chung ta nhận thấy là số lượng số 0 ở cuối của một số là min(số lượng số 2, và số lượng số 5) - khi phân tích ra thừa số nguyên tố
- Sau khi nhận thấy điều trên, ta thấy rằng một giai thừa thì trước một số là bội của 5 (như 5, 10, 15, 20, 25,...) thì trước đó nó luôn có một số nào đó là số chẵn (ý muốn nói là có chứa số 2 ở trong khi phân tích ra thừa số nguyên tố)
- Từ tất cả điều trên, bài này ta chỉ việc kiểu tra có bao nhiêu thừa số nguyên tố 5 (khi phân tích tất cả các số từ 1 tới n ra các thừa số nguyên tố).
- Để làm bài này có nhiều cách:
Cách 1:
- kiểm tra có bao nhiêu số là bội của 5, tiếp đó kiểm tra bao nhiêu số là bội của 25, 5mũ3, 5mũ4,... rồi ta tính tổng các kết quả lại với nhau là được
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
for(int i=0; i<t; ++i){
long long n; cin >> n;
long long ans=0; // nhớ để đáp án kiểu dữ liệu long long nha, 1e16/5 cũng lớn hơn 1e15 đó nha
// sau này chủ động dùng cái "#define int long long" trong code sẽ không phải lo tràn số, hoặc dễ dàng fix bug những bày cần thay đổi kiểu int sang long long, mà không cần phải sửa lại từng dòng
// không thì có thể thế dùng các define hoặc các cách khác như
//"define ll long long" nó thay thế chữ ll thành cụm từ phía sau (vì thế không đặt dấu chấm phẩy vào sau nha - cái này gọi là pre processor hay gì đó).
// "using ll = long long ll;" (có chấm phẩy nè - vì nó là câu lệnh)
// "typedef long long myLongLong;"
for(long long cur=5; cur<=n && cur>0; cur*=5){
ans+=n/cur;
}
cout <<ans <<'\n';
}
return 0;
}
Cách 2
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
for(int i=0; i<t; ++i){
long long n; cin >> n;
long long ans=0;
for( ; n>0 ; ){
ans+=n/5;
n/=5;
}
cout <<ans <<'\n';
}
return 0;
}
Bình luận