Hướng dẫn giải của Tin 10 Bài 6: Chia 3
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 số nguyên chia hết cho 3 trong đoạn [A, B] với A, B ≤ 2·10^9, nên dùng long long.
Sub 1: Duyệt từng số trong đoạn — ~O(B − A)~
Duyệt x từ A đến B, nếu x chia hết cho 3 thì tăng bộ đếm. Đúng nhưng đoạn có thể dài tới 2·10^9.
Kết quả chấm: đạt 14/20 test, 6 test quá thời gian, không sai test nào.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b;
cin >> a >> b;
// Vét cạn: duyệt từng số x trong đoạn [A, B] và đếm số chia hết cho 3
long long dem = 0;
for (long long x = a; x <= b; x++)
if (x % 3 == 0) dem++;
cout << dem << "\n";
return 0;
}
Sub 2: Công thức đếm bội — ~O(1)~
Số bội của 3 không vượt quá x là ⌊x/3⌋. Vậy số bội của 3 trong [A, B] là ⌊B/3⌋ − ⌊(A−1)/3⌋.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b;
cin >> a >> b; // B <= 2*10^9 nên dùng long long
// Số bội của 3 không vượt quá x: floor(x / 3). Đoạn [A, B] có floor(B/3) - floor((A-1)/3) số
cout << b / 3 - (a - 1) / 3 << "\n";
return 0;
}
Bình luận