Hướng dẫn giải của [Beginner Free Contest 06] DIVISIBLE
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ố ~x~ trong ~[L, R]~ chia hết cho 4, 7 hoặc 11. Số 0 cũng được tính vì 0 chia hết cho mọi số.
Sub 1: Duyệt trực tiếp — ~O(R - L)~, dùng khi ~R \le 10^6~
Duyệt từng ~x~ trong đoạn và kiểm tra. Nếu chỉ nộp sub này: đúng 6/10 test.
Sub 2: Nguyên lý bù trừ — ~O(1)~ mỗi test
Đặt ~h(n)~ là số bội của 4, 7 hoặc 11 trong ~[1, n]~: ~h(n) = n/4 + n/7 + n/11 - n/28 - n/44 - n/77 + n/308~. Đáp án là ~h(R) - h(L-1)~, cộng thêm 1 nếu ~L = 0~ vì số 0 được tính. Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
~main~ đọc ~T~ đoạn, nếu mọi ~R \le 10^6~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int T;
long long Lb[25], Rb[25];
// h(n) = so x trong [1, n] chia het cho 4, 7 hoac 11 (nguyen ly bu tru)
// lcm(4,7)=28, lcm(4,11)=44, lcm(7,11)=77, lcm(4,7,11)=308
long long h(long long n) {
if (n <= 0) return 0;
return n / 4 + n / 7 + n / 11 - n / 28 - n / 44 - n / 77 + n / 308;
}
// Sub 1: R <= 10^6, duyet truc tiep tung x trong [L, R]
void sub1() {
for (int i = 0; i < T; i++) {
long long cnt = 0;
for (long long x = Lb[i]; x <= Rb[i]; x++)
if (x % 4 == 0 || x % 7 == 0 || x % 11 == 0) cnt++;
cout << cnt << "\n";
}
}
// Sub 2: cong thuc bu tru, moi test O(1). So 0 chia het cho moi so nen neu L = 0 thi cong them 1.
void sub2() {
for (int i = 0; i < T; i++) {
long long ans = h(Rb[i]) - h(Lb[i] - 1) + (Lb[i] == 0 ? 1 : 0);
cout << ans << "\n";
}
}
int main() {
cin >> T;
long long mx = 0;
for (int i = 0; i < T; i++) {
cin >> Lb[i] >> Rb[i];
mx = max(mx, Rb[i]);
}
if (mx <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận