Hướng dẫn giải của Đếm số 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 x \le K sao cho x chia hết cho ít nhất một ai. Dùng nguyên lý bù trừ theo tập con các ai. Nếu lcm của một tập con vượt quá K thì không có bội nào \le K.
Sub 1: Thử từng số — ~O(K \cdot m)~, dùng khi ~K \le 10^6~
Với mỗi x từ 1 đến K, kiểm tra x có chia hết cho một a_i nào không. Nếu chỉ nộp sub này: đúng 14/20 test.
Sub 2: Nguyên lý bù trừ — ~O(2^m)~ (cắt nhánh khi lcm > K)
Với mỗi tập con S khác rỗng, số bội của lcm(S) trong [1..K] là \lfloor K / lcm(S) \rfloor. Cộng nếu |S| lẻ, trừ nếu |S| chẵn. Duyệt tập con bằng đệ quy và cắt nhánh khi lcm > K, vì mọi tập cha của nó cũng có lcm > K.
Bẫy: lcm(L, a) = L / gcd(L, a) \cdot a với L \le K \le 10^9 và a \le 10^9, tích vẫn nằm trong long long.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc K và dãy a. Nếu K \le 10^6 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long K;
int m;
vector<long long> a; // a[0..m-1]
long long res = 0;
// Sub 1: vet can. Thu tung so x = 1..K, neu x chia het cho mot a_i thi dem. O(K * m). Dung khi K <= 10^6
void sub1() {
long long cnt = 0;
for (long long x = 1; x <= K; x++) {
for (int i = 0; i < m; i++)
if (x % a[i] == 0) { cnt++; break; }
}
cout << cnt << "\n";
}
// Sub 2: nguyen ly bu tru. Voi moi tap con S (khac rong) cua {a_i}, so boi cua lcm(S) trong [1..K] la K / lcm(S).
// Dau cong neu |S| le, dau tru neu |S| chan. Duyet tap con bang de quy, cat nhanh khi lcm > K
// (khi do moi tap cha cung khong co boi nao <= K). Dung cho moi K.
void dfs(int idx, long long L, int sz) {
for (int i = idx; i < m; i++) {
long long nl = L / __gcd(L, a[i]) * a[i]; // lcm(L, a_i), L <= K nen khong tran so
if (nl > K) continue;
long long c = K / nl;
if ((sz + 1) % 2 == 1) res += c; else res -= c;
dfs(i + 1, nl, sz + 1);
}
}
void sub2() {
res = 0;
dfs(0, 1, 0);
cout << res << "\n";
}
int main() {
freopen("CHIAHET.INP", "r", stdin);
freopen("CHIAHET.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> K >> m;
a.assign(m, 0);
for (int i = 0; i < m; i++) cin >> a[i];
if (K <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận