Hướng dẫn giải của Chia hết
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 các số trong ~[a, b]~ chia hết cho ~x~ hoặc ~y~. Bài toán này có thể giải bằng nguyên lý bù trừ.
Sub 1: Vét cạn — ~O(b - a)~, dùng khi ~b \le 10^6~
Duyệt từng số ~i~ trong ~[a, b]~, đếm nếu ~i~ chia hết cho ~x~ hoặc ~y~.
Nếu chỉ nộp sub này: đúng 17/20 test.
Sub 2: Nguyên lý bù trừ — ~O(1)~
Số bội của ~d~ trong ~[a, b]~ là ~\lfloor b/d \rfloor - \lfloor (a-1)/d \rfloor~. Đáp án là bội của ~x~ cộng bội của ~y~ trừ bội của ~BCNN(x, y)~ (để không đếm hai lần). ~BCNN~ không vượt quá ~10^{18}~ nên long long là đủ.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Dữ liệu ~b \le 10^6~ dùng sub 1, còn lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
long long a, b, x, y;
// Sub 1: vet can, duyet tung so trong [a, b]. Dung khi b <= 10^6.
void sub1() {
long long cnt = 0;
for (long long i = a; i <= b; i++)
if (i % x == 0 || i % y == 0) cnt++;
cout << cnt << "\n";
}
// Sub 2: nguyen ly bu tru. Dem boi cua x + boi cua y - boi cua BCNN(x, y).
// Ham f(n) = so boi trong [1, n]; so boi trong [a, b] = f(b) - f(a-1).
void sub2() {
long long l = x / __gcd(x, y) * y; // BCNN, <= 10^18 nen khong tran long long
auto cntDiv = [&](long long d) { return b / d - (a - 1) / d; };
cout << cntDiv(x) + cntDiv(y) - cntDiv(l) << "\n";
}
int main() {
cin >> a >> b >> x >> y;
if (b <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận