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 số nguyên trong đoạn [a, b] chia hết cho x hoặc chia hết cho y (a, b, x, y ≤ 10^9).
Sub 1: Vét cạn — ~O(b - a)~
Duyệt từng số i trong [a, b], kiểm tra i chia hết cho x hoặc y rồi đếm. Đúng với mọi test nhỏ nhưng khoảng cách b - a có thể lên tới 10^9 nên chậm.
Kết quả chấm: 17/20 (SUB ok 17/20, TLE 3, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU2.INP", "r")) { freopen("CAU2.INP", "r", stdin); freopen("CAU2.OUT", "w", stdout); }
long long a, b, x, y;
cin >> a >> b >> x >> y;
long long dem = 0;
// Vet can: duyet tung so i trong [a, b] va kiem tra chia het cho x hoac y
for (long long i = a; i <= b; i++)
if (i % x == 0 || i % y == 0) dem++;
cout << dem << "\n";
return 0;
}
Sub 2: Nguyên lý bù trừ — ~O(\log(\min(x,y)))~
Đếm số bội của x trên [1, n] là n / x, của y là n / y. Số chia hết cho cả hai được đếm hai lần nên phải trừ đi n / BCNN(x, y). Đếm trên [a, b] bằng f(b) - f(a - 1).
Bẫy: BCNN(x, y) = x / gcd(x, y) * y, phải tính theo thứ tự này và dùng long long để không tràn số.
Kết quả chấm: 20/20
#include <bits/stdc++.h>
using namespace std;
// So cac so nguyen duong trong [1, n] chia het cho x hoac y
long long demChiaHet(long long n, long long x, long long y) {
long long l = x / __gcd(x, y) * y; // BCNN(x, y), co the lon nhung khong tran vi x, y <= 10^9
return n / x + n / y - n / l; // nguyen tac bu tru: so chia het cho ca hai duoc dem 2 lan nen tru 1 lan
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU2.INP", "r")) { freopen("CAU2.INP", "r", stdin); freopen("CAU2.OUT", "w", stdout); }
long long a, b, x, y;
cin >> a >> b >> x >> y;
// Dem tren [a, b] = dem tren [1, b] - dem tren [1, a-1]
cout << demChiaHet(b, x, y) - demChiaHet(a - 1, x, y) << "\n";
return 0;
}
Bình luận