Hướng dẫn giải của Tin 10 Bài 9: 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 dương không lớn hơn ~n~ mà chia hết cho ~a~ hoặc ~b~, với ~n \le 10^{18}~. Dùng nguyên lý bù trừ: số cần đếm = ~\lfloor n/a \rfloor + \lfloor n/b \rfloor - \lfloor n/BCNN(a,b) \rfloor~.
Sub 1: Vét cạn — ~O(n)~, dùng khi ~n \le 10^6~
Duyệt ~i~ từ ~1~ đến ~n~, đếm ~i~ nếu ~i \% a = 0~ hoặc ~i \% b = 0~. Nếu chỉ nộp sub này: đúng 20/24 test.
Sub 2: Nguyên lý bù trừ — ~O(\log n)~
Dùng công thức trên. Bẫy: ~BCNN(a,b) = (a / \gcd(a,b)) \cdot b~ có thể vượt ~10^{18}~ và tràn số. Vì vậy chỉ trừ phần ~n / BCNN~ khi ~(a / \gcd) \le \lfloor n/b \rfloor~, tức là BCNN không vượt ~n~. 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~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long n, a, b;
// Sub 1: vet can. Duyet i tu 1 den n, dem so chia het cho a hoac b. O(n). Dung khi n <= 10^6.
void sub1() {
long long cnt = 0;
for (long long i = 1; i <= n; i++)
if (i % a == 0 || i % b == 0) cnt++;
cout << cnt << "\n";
}
// Sub 2: nguyen ly bu tru: n/a + n/b - n/BCNN(a,b). O(log).
// BCNN(a,b) = (a/g)*b co the tran so, nen chi tinh khi t*b <= n.
void sub2() {
long long g = __gcd(a, b);
long long t = a / g;
long long cnt = n / a + n / b;
if (t <= n / b) cnt -= n / (t * b);
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> a >> b;
if (n <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận