Hướng dẫn giải của Đếm số (đề Cần Thơ 2021)
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
Cần đếm các số a trong dãy thỏa mãn a chia hết cho 3 nhưng không chia hết cho 9. Với mỗi số, chỉ cần kiểm tra hai điều kiện trên; các số có giá trị tuyệt đối đến 10^9 nên dùng long long.
Sub 1: Vét cạn bằng phép trừ dần — ~O(n \cdot \max|a| / m)~
Kiểm tra "a chia hết cho m" bằng cách trừ dần m khỏi |a| cho đến khi nhỏ hơn m. Đúng nhưng với số lớn (gần 10^9) mỗi lần kiểm tra tốn nhiều bước.
Kết quả chấm: đạt 17/25 test, 8 test quá thời gian, không sai test nào.
#include <bits/stdc++.h>
using namespace std;
// Kiểm tra chia hết bằng cách trừ dần m (vét cạn, chậm với số lớn)
bool chiaHet(long long x, long long m) {
x = llabs(x);
while (x >= m) x -= m;
return x == 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("DEMSO.INP", "r")) {
freopen("DEMSO.INP", "r", stdin);
freopen("DEMSO.OUT", "w", stdout);
}
int n;
cin >> n;
int dem = 0;
for (int i = 0; i < n; i++) {
long long a;
cin >> a;
// chia hết cho 3 và không chia hết cho 9
if (chiaHet(a, 3) && !chiaHet(a, 9)) dem++;
}
cout << dem << "\n";
return 0;
}
Sub 2: Dùng phép chia lấy dư — ~O(n)~
Dùng toán tử %: a chia hết cho 3 khi a % 3 == 0, không chia hết cho 9 khi a % 9 != 0. Phép % của số âm vẫn cho 0 khi chia hết nên không cần xử lý riêng dấu.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("DEMSO.INP", "r")) {
freopen("DEMSO.INP", "r", stdin);
freopen("DEMSO.OUT", "w", stdout);
}
int n;
cin >> n;
int dem = 0;
for (int i = 0; i < n; i++) {
long long a; // |a| <= 10^9 nên dùng long long cho an toàn
cin >> a;
// Phép % cho kết quả 0 khi a chia hết (kể cả a âm, vì -6 % 3 == 0)
if (a % 3 == 0 && a % 9 != 0) dem++;
}
cout << dem << "\n";
return 0;
}
Bình luận