Hướng dẫn giải của Chia hết (đề THCS Phú Thọ 2023-2024)
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 dương ~x \le n~ thỏa mãn ~x \ mod\ a = 0~ hoặc ~x \ mod\ b = 0~. Với ~n \le 10^{18}~ thì không thể duyệt hết các số.
Sub 1: Vét cạn — ~O(n)~, dùng khi ~n \le 10^6~
Xét lần lượt ~x = 1, 2, \ldots, n~, kiểm tra chia hết cho ~a~ hoặc ~b~ rồi đếm. Nếu chỉ nộp sub này: đúng 20/24 test (đúng hết các test trong miền, 4 test lớn bị quá giờ).
Sub 2: Công thức loại trừ — ~O(\log \min(a,b))~
Theo nguyên lý bao hàm – loại trừ: số chia hết cho ~a~ hoặc ~b~ bằng ~\lfloor n/a \rfloor + \lfloor n/b \rfloor - \lfloor n / BCNN(a,b) \rfloor~. Bẫy cần chú ý: ~BCNN(a,b) = a / \gcd(a,b) \cdot b~ có thể vượt quá ~10^{18}~ và bị tràn số. Vì vậy kiểm tra trước: nếu ~a / \gcd \le n / b~ thì ~BCNN \le n~ và mới tính ~n / BCNN~; nếu không thì số hạng đó bằng 0. Nếu chỉ nộp sub này: đúng 24/24 test.
Chương trình hoàn chỉnh
main đọc ~n, a, b~. Nếu ~n \le 10^6~ thì gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long n, a, b;
// Sub 1: vet can O(n) - xet tung so tu 1 den n, dem so chia het cho a hoac b. Dung khi n <= 10^6.
void sub1() {
long long cnt = 0;
for (long long x = 1; x <= n; x++)
if (x % a == 0 || x % b == 0) cnt++;
cout << cnt << "\n";
}
// Sub 2: cong thuc bao ham - loai tru
// So chia het cho a hoac b = n/a + n/b - n/BCNN(a, b)
void sub2() {
long long g = __gcd(a, b);
long long cnt = n / a + n / b;
// BCNN(a, b) = a / g * b. Neu BCNN > n thi n / BCNN = 0, tranh tran so bang cach kiem tra truoc.
long long q = a / g;
if (q <= n / b) { // khi do q * b <= n, BCNN khong vuot n
long long l = q * b;
cnt -= n / l;
}
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> a >> b;
if (n <= 1000000) sub1(); // subtask 1
else sub2(); // subtask 2
return 0;
}
Bình luận