Công thức Bao hàm - Loại trừ
I. Mở đầu
Công thức bao hàm - loại trừ là một công thức sử dụng để tính lực lượng (số lượng phần tử) của hợp của nhiều tập hợp. Công thức được phát biểu như sau: "Để tính lực lượng của hợp của nhiều tập hợp, ta tính tổng lực lượng các tập hợp đó, rồi trừ đi lực lượng của giao của các cặp hai tập hợp khác nhau, rồi cộng lực lượng của giao các bộ ba tập hợp khác nhau, rồi trừ đi lực lượng của các bộ bốn tập hợp, và cứ thế cho đến khi ta xét đến giao của tất cả các tập hợp."
Đối với các tập hợp, công thức có thể được viết ở dạng như sau: Giả sử có tập hợp . Lực lượng của hợp của tập hợp là:
Ta có thể minh họa công thức bằng một sơ đồ Venn trong trường hợp như sau:
Như sơ đồ, ta thấy lực lượng của bằng tổng lực lượng của trừ đi lực lượng của các giao rồi cộng thêm lực lượng của :
Bằng phương pháp tương tự ta có thể minh họa được công thức với tập hợp.
Ví dụ: Đếm số lượng số từ tới và không chia hết cho số nào trong tập :
Ta có thể biến đổi bài toán thành đếm phần bù: Đếm số lượng phần tử chia hết cho ít nhất một số trong tập rồi lấy trừ đi số lượng đó. Đặt là tập hợp các phần tử chia hết cho là tập hợp các phần tử chia hết cho là tập hợp các phần tử chia hết cho từ 1 tới . Cần tính . Dựa vào công thức bao hàm, loại trừ, ta có:
Đoạn mã tính toán công thức trên có thể viết đơn giản như sau:
int count_numbers(int N)
{
return N - N / 2 - N / 3 - N / 5 + N / (2 * 3) +
N / (3 * 5) + N / (2 * 5) - N / (2 * 3 * 5);
}
Công thức bao hàm - loại trừ có sức mạnh cực kì to lớn trong các bài toán đếm của toán học tổ hợp. Sau đây chúng ta sẽ cùng nghiên cứu một số bài toán ứng dụng của công thức này!
II. Bài toán ví dụ
1. Chính phương và Lập phương
Đề bài
Dãy số chính phương và lập phương là dãy gồm các số chính phương và lập phương. Sau đây là một vài số đầu tiên trong dãy:
Yêu cầu: Cho số nguyên dương . Hãy xác định trong đoạn có bao nhiêu số nằm trong dãy số chính phương và lập phương.
Input:
- Dòng đầu tiên chứa số nguyên — số lượng test case.
- dòng tiếp theo tương ứng với test case, mỗi dòng chứa số nguyên .
Ràng buộc:
- .
- .
Output:
- Gồm dòng là kết quả tương ứng với test case.
Sample Input:
6
10
1
25
1000000000
999999999
500000000
Sample Output:
4
1
6
32591
32590
23125
Ý tưởng
Dãy số gồm các số chính phương sẽ là dãy gồm các số có dạng với và .
Tương tự, dãy số gồm các số lập phương sẽ là dãy gồm các số có dạng với và .
Tuy nhiên, trong hai dãy số đó sẽ có những số bị trùng nhau, tức là vừa là số chính phương, vừa là số lập phương. Các số đó có dạng với và . Ta sẽ tạo ra dãy gồm các số chính phương, dãy gồm các số lập phương và dãy gồm các số dạng lũy thừa bậc .
Gọi là số lượng số chính phương không vượt quá là số lượng số lập phương không vượt quá và là số lượng số vừa là chính phương vừa là lập phương không vượt quá . Ba giá trị này có thể dễ dàng tính ra được bằng cách tìm kiếm nhị phân trên ba mảng . Sau đó, theo công thức bao hàm loại trừ, số lượng số nằm trong dãy chính phương - lập phương từ tới sẽ là:
Để đẩy nhanh tốc độ giải thuật, ta sẽ khởi tạo trước ba mảng tới các số không vượt quá rồi ứng với mỗi giá trị ở từng test case thì thực hiện tìm kiếm nhị phân và tính toán như công thức nói trên.
Độ phức tạp: .
Cài đặt
#include <bits/stdc++.h>
using namespace std;
vector < int > a, b, c;
void init()
{
for (int i = 1; i * i <= 1e9; ++i)
a.push_back(i * i);
for (int i = 1; i * i * i <= 1e9; ++i)
b.push_back(i * i * i);
for (int i = 1; i * i * i * i * i * i <= 1e9; ++i)
c.push_back(i * i * i * i * i * i);
}
void solve_testcase(int n)
{
int cnt1 = (upper_bound(a.begin(), a.end(), n) - a.begin());
int cnt2 = (upper_bound(b.begin(), b.end(), n) - b.begin());
int cnt3 = (upper_bound(c.begin(), c.end(), n) - c.begin());
cout << cnt1 + cnt2 - cnt3 << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
init();
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
solve_testcase(n);
}
return 0;
}
2. Ba - Năm - Bảy
Đề bài
Thầy giáo cho UcoderA định nghĩa về dãy số ba - năm - bảy như sau: Là một dãy số tăng dần, các phần tử của dãy chia hết cho ít nhất một trong ba số , và . Ví dụ một vài phần tử đầu tiên của dãy:
Yêu cầu: Cho số nguyên hãy xác định giá trị phần tử thứ của dãy số ba - năm - bảy?
Input:
- Một dòng duy nhất chứa số nguyên .
Ràng buộc:
- .
Output:
- Phần tử thứ của dãy số ba-năm-bảy.
Sample Input 1
13
Sample Output 1
24
Sample Input 2
100
Sample Output 2
185
Ý tưởng
Với các subtask nhỏ, ta có thể sử dụng vòng lặp sau đó tăng dần số đang xét cho đến khi đó là phần tử thứ ở trong dãy ba-năm-bảy.
Độ phức tạp thuật toán lúc này là . Ta cần một thuật toán tốt hơn.
Để cải tiến cách làm, các bạn cần sử dụng chặt nhị phân và kiến thức về bao hàm bù trừ.
Với mỗi số ta có thể xác định được trước nó có bao nhiêu số chia hết cho hoặc bằng cách sau:
Gọi số lượng số bé hơn hoặc bằng chia hết cho là , định nghĩa tương tự cho và . Số lượng số chia hết cho cả và là , định nghĩa tương tự cho và . Số lượng số chia hết cho cả , và là .
Ta thấy rằng tổng sẽ bị trùng với nhau một lượng phần , và nên ta phải trừ đi lượng đấy, nhưng nếu trừ đi thì ta sẽ mất một lượng nên phải cộng bù vào. Vậy số lượng số chia hết cho , hoặc bé hơn hoặc bằng là:
Có được công thức trên, bạn đọc có thể sử dụng kĩ thuật chặt nhị phân tìm kết quả để tìm số bé nhất sao cho từ đến có đúng số chia hết cho , hoặc .
Độ phức tạp thuật toán: .
Cài đặt
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll k;
cin >> k;
ll l = 3, r = 2e18, ans;
while(l <= r)
{
ll x = (l + r) / 2LL;
ll cnt3 = x / 3LL;
ll cnt5 = x / 5LL;
ll cnt7 = x / 7LL;
ll cnt15 = x / 15LL;
ll cnt21 = x / 21LL;
ll cnt35 = x / 35LL;
ll cnt105 = x / 105LL;
if (cnt3 + cnt7 + cnt5 - cnt15 - cnt21 - cnt35 + cnt105 >= k)
r = x - 1, ans = x;
else
l = x + 1;
}
cout << ans;
return 0;
}
3. Dãy chữ số đầy đủ
Đề bài
Cho trước số nguyên dương . Một dãy được gọi là dãy đầy đủ nếu thỏa mãn những điều sau đây:
- .
- Tồn tại một vị trí nào đó sao cho .
- Tồn tại một vị trí nào đó sao cho .
Yêu cầu: Hãy đếm số số dãy đẩy đủ có độ dài . Kết quả có thể rất lớn, hãy in ra số dư khi chia cho .
Input:
- Dòng duy nhất chứa một số .
Constraints:
- .
Output:
- Một số duy nhất là số dư của kết quả sau khi chia cho .
Sample Input 1:
2
Sample Output 1:
2
Giải thích:
Có dãy là và .
Ý tưởng
Có tổng cộng dãy độ dài và .
Thay vì đếm trực tiếp, ta sẽ sử dụng kĩ thuật đếm phần bù trong bài toán này. Cụ thể, ta sẽ trừ đi những dãy không phải là dãy đầy đủ, hay những dãy không tồn tại hoặc không tồn tại . Số lượng đó như sau:
- Có tổng cộng dãy không tồn tại .
- Có tổng cộng dãy không tồn tại .
- Có tổng cộng dãy không tồn tại và .
Theo nguyên lí bao hàm - loại trừ, ta suy ra có dãy không tồn tại hoặc không tồn tại .
Như vậy đáp án là .
Độ phức tạp: hoặc tùy vào cài đặt để tính các lũy thừa. Lưu ý kết quả có phép trừ, do đó nếu sử dụng ngôn ngữ C++ thì cần chú ý tránh để xảy ra trường hợp kết quả bị âm sau khi chia dư cho .
Cài đặt
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int binary_exponentiation(int a, int b, int mod)
{
if (b == 0)
return 1LL;
int half = binary_exponentiation(a, b / 2LL, mod) % mod;
if (b & 1)
return (((half * half) % mod) * (a % mod)) % mod;
else
return (half * half) % mod;
}
main()
{
int n;
cin >> n;
int x = binary_exponentiation(10, n, mod);
int y = (2 * binary_exponentiation(9, n, mod) % mod - binary_exponentiation(8, n, mod) + mod) % mod;
cout << (x - y + mod) % mod;
return 0;
}
III. Tài liệu tham khảo
- https://www.geeksforgeeks.org/eulerian-number/
- https://vnoi.info/wiki/translate/he/Number-Theory-5
- https://www.hackerearth.com/practice/notes/number-theory-ii/
- https://vnoi.info/wiki/translate/he/Number-Theory-7.md
- Tài liệu giáo khoa chuyên Tin quyển 1 - thầy Hồ Sĩ Đàm
©️ Tác giả: Vũ Quế Lâm từ Viblo
All rights reserved