Hướng dẫn giải của [200 đề thầy Đức] Bài 15: Đếm bội số
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
Cho đoạn $[L, R]$ và hai số $a, b$, cần đếm các số trong đoạn chia hết cho $a$ hoặc $b$. Với $T$ bộ dữ liệu, mỗi bộ có $R$ tới $10^9$ nên không thể duyệt hết mọi số trong đoạn cho mọi bộ.
Sub 1: Vét cạn — ~O(R - L)~ mỗi bộ, dùng khi ~R - L \le 10^6~
Duyệt từng số $x$ trong $[L, R]$ và kiểm tra $x$ có chia hết cho $a$ hoặc $b$ hay không. Cách này đúng với mọi đoạn, nhưng với đoạn dài thì chậm.
Nếu chỉ nộp sub này: đúng 21/21 test.
Sub 2: Nguyên lý bù trừ — ~O(1)~ mỗi bộ
Số bội của $a$ trong $[1, x]$ là $\lfloor x/a \rfloor$, tương tự với $b$. Các số vừa là bội của $a$ vừa là bội của $b$ chính là bội của $\text{lcm}(a, b)$, nên được đếm hai lần và cần trừ đi một lần:
$$\text{dem}(x) = \lfloor x/a \rfloor + \lfloor x/b \rfloor - \lfloor x/\text{lcm}(a,b) \rfloor$$
Đáp án của đoạn $[L, R]$ là $\text{dem}(R) - \text{dem}(L-1)$.
Bẫy cần chú ý: $\text{lcm}(a,b)$ được tính bằng $a / \gcd(a,b) \cdot b$ (chia trước khi nhân) và giá trị đủ nhỏ ($a, b \le 10^4$) nên không tràn. Kết quả có thể lớn nên dùng long long.
Chương trình hoàn chỉnh
Chương trình đọc toàn bộ $T$ bộ dữ liệu. Nếu mọi đoạn đều ngắn ($R - L \le 10^6$) thì gọi sub1, ngược lại gọi sub2. Khi đi thi có thể viết như vậy: nếu sub2 sai thì vẫn có điểm cho sub1 trên các bài nhỏ.
#include <bits/stdc++.h>
using namespace std;
int T;
long long L[105], R[105], A[105], B[105];
// Sub 1: vét cạn — duyệt từng số trong [L, R], kiểm tra có chia hết a hoặc b
// Dùng khi R - L <= 10^6 cho mọi bộ dữ liệu
void sub1() {
for (int t = 1; t <= T; t++) {
long long cnt = 0;
for (long long x = L[t]; x <= R[t]; x++)
if (x % A[t] == 0 || x % B[t] == 0) cnt++;
cout << cnt << "\n";
}
}
// Sub 2: nguyên lý bù trừ — đếm bội của a trong [1, x] là x/a,
// bội chung của a và b là lcm(a,b). Số bội của a hoặc b trong [1, x] = x/a + x/b - x/lcm
long long countUpTo(long long x, long long a, long long b) {
long long l = a / __gcd(a, b) * b; // lcm(a, b), không tràn vì a, b <= 10^4
return x / a + x / b - x / l;
}
// Sub 2: O(1) cho mỗi bộ dữ liệu, dùng cho R lớn
void sub2() {
for (int t = 1; t <= T; t++) {
// đếm trên [L, R] = đếm trên [1, R] - đếm trên [1, L-1]
long long ans = countUpTo(R[t], A[t], B[t]) - countUpTo(L[t] - 1, A[t], B[t]);
cout << ans << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
bool small = true;
for (int t = 1; t <= T; t++) {
cin >> L[t] >> R[t] >> A[t] >> B[t];
if (R[t] - L[t] > 1000000) small = false;
}
if (small) sub1(); // đoạn ngắn: vét cạn cho chắc
else sub2(); // đoạn dài: bù trừ
return 0;
}
Bình luận