Nguyên lý bù trừ

Mức độ: Cơ bản

Khi đếm theo từng nhóm mà các nhóm chồng lên nhau, cộng thẳng sẽ đếm một số phần tử nhiều lần. Nguyên lý bù trừ sửa lỗi đó: cộng, rồi trừ phần bị đếm thừa, rồi cộng lại phần bị trừ thừa… Các bạn đã gặp ý này ở bài chia hết cho 3 hoặc 5.

Hai tập hợp

Lớp có 40 bạn: 22 bạn thích bóng đá, 18 bạn thích cầu lông, 8 bạn thích cả hai. Bao nhiêu bạn thích ít nhất một môn?

Cộng 22 + 18 = 40 thì 8 bạn thích cả hai bị đếm hai lần. Trừ đi một lần: 22 + 18 - 8 = 32 bạn. Số bạn không thích môn nào: 40 - 32 = 8.

|A ∪ B| = |A| + |B| - |A ∩ B| (|A| là số phần tử của A, A ∪ B là “thuộc A hoặc B”, A ∩ B là “thuộc cả A và B”).

Ba tập hợp

Với ba môn A, B, C, xét một bạn thích cả ba môn:

Bước	Phép tính	Bạn đó được đếm
Cộng từng môn	|A| + |B| + |C|	3 lần
Trừ từng cặp	- |A ∩ B| - |A ∩ C| - |B ∩ C|	3 - 3 = 0 lần
Cộng cả ba	+ |A ∩ B ∩ C|	1 lần

Kiểm tra tương tự với bạn chỉ thích một hoặc hai môn, đều được đếm đúng 1 lần. Vậy:

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

Quy luật chung: giao của số lẻ tập thì cộng, số chẵn tập thì trừ.

Đếm số chia hết: duyệt mọi tập con

Đếm số từ 1 đến n chia hết cho ít nhất một trong k số a₁, …, a_k. Tập “chia hết cho a_i” có n // a_i phần tử, giao của nhiều tập là các số chia hết cho bội chung nhỏ nhất của chúng. Có 2^k - 1 nhóm khác rỗng, duyệt hết bằng số nhị phân: bit thứ i bằng 1 nghĩa là chọn a_i.

Python

from math import gcd

def dem_chia_het_it_nhat_mot(n, a):
    k = len(a)
    tong = 0
    for mask in range(1, 1 << k):          # mọi nhóm con khác rỗng
        l, so_luong = 1, 0
        for i in range(k):
            if mask >> i & 1:               # nhóm có chọn a[i]
                l = l // gcd(l, a[i]) * a[i]
                so_luong += 1
        if so_luong % 2 == 1:
            tong += n // l                  # nhóm lẻ: cộng
        else:
            tong -= n // l                  # nhóm chẵn: trừ
    return tong

print(dem_chia_het_it_nhat_mot(1000, [3, 5, 7]))   # 543

C++

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

long long demChiaHetItNhatMot(long long n, const vector<long long>& a) {
    int k = a.size();
    long long tong = 0;
    for (int mask = 1; mask < (1 << k); mask++) {   // mọi nhóm con khác rỗng
        long long l = 1;
        int soLuong = 0;
        for (int i = 0; i < k; i++) {
            if (mask >> i & 1) {                     // nhóm có chọn a[i]
                soLuong++;
                long long g = gcd(l, a[i]);
                if (l / g > n / a[i]) {              // bội chung sẽ vượt n: n / l = 0
                    l = n + 1;
                    break;
                }
                l = l / g * a[i];
            }
        }
        if (soLuong % 2 == 1) tong += n / l;
        else tong -= n / l;
    }
    return tong;
}

int main() {
    cout << demChiaHetItNhatMot(1000, {3, 5, 7}) << endl;   // 543
    return 0;
}

Lưu ý: trong C++, bội chung nhỏ nhất của nhiều số có thể tràn long long. Phải kiểm tra trước khi nhân: nếu l / g > n / a[i] thì tích chắc chắn lớn hơn n, khi đó n / l = 0 nên gán l = n + 1 rồi dừng. Nhân trước rồi mới so sánh thì tích có thể đã tràn thành số sai.

Hoán vị không điểm cố định: đổi quà

n bạn mỗi người mang một món quà, bỏ vào hộp rồi rút ngẫu nhiên. Có bao nhiêu cách để không ai rút được quà của mình? Gọi A_i là các cách bạn i rút đúng quà mình. Bù trừ cho:

D(n) = n! - C(n, 1)(n - 1)! + C(n, 2)(n - 2)! - … = n! × (1 - 1/1! + 1/2! - 1/3! + … ± 1/n!)

n	1	2	3	4	5	6	7
D(n)	0	1	2	9	44	265	1854

Khi lập trình, dùng công thức truy hồi gọn hơn: D(n) = (n - 1) × (D(n - 1) + D(n - 2)), với D(1) = 0, D(2) = 1.

Chia kẹo có giới hạn

Chia 10 viên kẹo giống nhau cho 3 bạn, mỗi bạn không quá 4 viên. Không giới hạn thì có C(12, 2) = 66 cách (kỹ thuật vách ngăn). Bỏ đi các cách có bạn nhận từ 5 viên trở lên: đưa trước cho bạn đó 5 viên, chia nốt 5 viên còn lại: C(7, 2) = 21 cách cho mỗi bạn, 3 bạn là 63. Hai bạn cùng từ 5 viên thì vừa hết 10 viên: C(2, 2) = 1 cách cho mỗi cặp, 3 cặp. Đáp số 66 - 63 + 3 = 6.

Luyện tập

Gồm 22 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Hai, ba tập hợp

Bài 1. Không thích môn nào

Lớp có n bạn, a bạn thích bóng đá, b bạn thích cầu lông, c bạn thích cả hai môn (mọi số ≤ 10⁹). Nhập n, a, b, c, in ra số bạn không thích môn nào.

Ví dụ: nhập 10 5 4 2 thì in ra 3.

Kiểm tra: nhập 40 22 18 8.

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Tìm số bạn của một môn

Lớp có n bạn. Có a bạn chơi bóng đá, c bạn chơi cả bóng đá và quần vợt, d bạn không chơi môn nào trong hai môn. Hỏi có bao nhiêu bạn chơi quần vợt? Nhập n, a, c, d.

Ví dụ: nhập 20 10 3 2 thì in ra 11.

Kiểm tra: nhập 35 22 8 6.

Xem đáp số

15

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Ba môn học

Lớp có n bạn. Nhập n và bảy số: số bạn thích Toán, Tin, Văn; số bạn thích Toán và Tin, Toán và Văn, Tin và Văn; số bạn thích cả ba môn. In ra số bạn không thích môn nào.

Ví dụ: nhập 10 4 5 3 2 1 1 1 thì in ra 1.

Kiểm tra: nhập 45 25 20 18 10 8 7 4.

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Chia hết cho 3, 5 hoặc 7

Nhập n (n ≤ 10¹⁸). Đếm các số từ 1 đến n chia hết cho ít nhất một trong ba số 3, 5, 7.

Ví dụ: nhập 20 thì in ra 11.

Kiểm tra: nhập 1000.

Xem đáp số

543

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Không chia hết cho 2, 3, 5

Nhập n (n ≤ 10¹⁸). Đếm các số từ 1 đến n không chia hết cho số nào trong ba số 2, 3, 5.

Ví dụ: nhập 30 thì in ra 8.

Kiểm tra: nhập 1000.

Xem đáp số

266

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Nhiều tập hợp, duyệt tập con

Bài 6. Chia hết cho ít nhất một số trong danh sách

Dòng đầu có n và k (n ≤ 10¹⁸, k ≤ 15). Dòng thứ hai có k số nguyên dương a_i ≤ 10⁹ (không nhất thiết nguyên tố cùng nhau). Đếm các số từ 1 đến n chia hết cho ít nhất một số a_i.

Ví dụ:

Nhập	In ra
100 3 4 6 10	36

Kiểm tra: nhập

1000000000000000000 3
4 6 10

Xem đáp số

366666666666666666

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Nguyên tố cùng nhau với m

Nhập n, m (n ≤ 10¹⁸, 2 ≤ m ≤ 10¹²). Đếm các số x từ 1 đến n mà x và m nguyên tố cùng nhau.

Ví dụ: nhập 10 10 thì in ra 4.

Kiểm tra: nhập 360 360.

Xem đáp số

96

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Chia hết cho đúng một trong hai số

Nhập n, a, b (n ≤ 10¹⁸, a, b ≤ 10⁹). Đếm các số từ 1 đến n chia hết cho đúng một trong hai số a, b (không tính số chia hết cho cả hai).

Ví dụ: nhập 10 2 3 thì in ra 6.

Kiểm tra: nhập 1000 2 3.

Xem đáp số

501

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Số chính phương hoặc lập phương

Nhập n (n ≤ 10¹⁸). Đếm các số từ 1 đến n là số chính phương (bình phương một số nguyên) hoặc số lập phương (lập phương một số nguyên).

Ví dụ: nhập 100 thì in ra 12.

Kiểm tra: nhập 1000000.

Xem đáp số

1090

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Trong đoạn, không chia hết cho số nào

Dòng đầu có L, R, k (1 ≤ L ≤ R ≤ 10¹⁸, k ≤ 15). Dòng thứ hai có k số a_i ≤ 10⁹. Đếm các số trong đoạn từ L đến R không chia hết cho số nào trong các a_i.

Ví dụ:

Nhập	In ra
1 10 2 2 3	3

Kiểm tra: nhập

100 1000 3
6 10 15

Xem đáp số

660

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Hoán vị và phân phối

Bài 11. Hai bạn không ở đúng chỗ của mình

n bạn (2 ≤ n ≤ 20) có ghế đánh số riêng. Xếp n bạn vào n ghế sao cho bạn số 1 không ngồi ghế 1 và bạn số 2 không ngồi ghế 2 (các bạn khác ngồi đâu cũng được). Có bao nhiêu cách?

Ví dụ: nhập 3 thì in ra 3.

Kiểm tra: nhập 6.

Xem đáp số

504

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Đổi quà

n bạn (1 ≤ n ≤ 20) mỗi người mang một món quà, bỏ chung rồi mỗi người rút một món. Có bao nhiêu cách rút mà không ai nhận lại quà của mình?

Ví dụ: nhập 4 thì in ra 9.

Kiểm tra: nhập 7.

Xem đáp số

1854

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Đổi quà với n lớn

Như bài 12 nhưng n ≤ 10⁶. In ra số cách chia lấy dư cho 10⁹ + 7.

Ví dụ: nhập 4 thì in ra 9.

Kiểm tra: nhập 1000000.

Xem đáp số

102701088

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Dùng đủ mọi màu

Tô n ô xếp thành hàng bằng k màu (kⁿ ≤ 10¹⁸), mỗi ô một màu, sao cho mỗi màu được dùng ít nhất một lần. Có bao nhiêu cách tô?

Ví dụ: nhập 5 3 thì in ra 150.

Kiểm tra: nhập 6 3.

Xem đáp số

540

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Không có hai số liên tiếp đứng cạnh nhau

Xếp các số 1, 2, …, n (n ≤ 12) thành một hàng sao cho không có chỗ nào số i đứng ngay trước số i + 1 (ví dụ không được có …3 4…). Có bao nhiêu cách?

Ví dụ: nhập 3 thì in ra 3.

Kiểm tra: nhập 5.

Xem đáp số

53

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Chia kẹo có giới hạn

Chia n viên kẹo giống nhau cho k bạn, mỗi bạn được từ 0 đến m viên, và chia hết số kẹo (n ≤ 1000, k ≤ 10, m ≤ 1000). Có bao nhiêu cách?

Ví dụ: nhập 10 3 4 thì in ra 6.

Kiểm tra: nhập 20 3 8.

Xem đáp số

15

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Xâu có cả chữ a và chữ b

Đếm các xâu độ dài n (n ≤ 12) gồm các chữ cái thường a đến z, chứa ít nhất một chữ a và ít nhất một chữ b.

Ví dụ: nhập 2 thì in ra 2.

Kiểm tra: nhập 5.

Xem đáp số

312750

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Vận dụng

Bài 18. Có cả chữ số 0 và chữ số 9

Nhập n (2 ≤ n ≤ 18). Đếm các số có đúng n chữ số chứa ít nhất một chữ số 0 và ít nhất một chữ số 9.

Ví dụ: nhập 2 thì in ra 1.

Kiểm tra: nhập 4.

Xem đáp số

703

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Hàm Euler

Nhập n (1 ≤ n ≤ 10¹²). In ra φ(n): số lượng số từ 1 đến n nguyên tố cùng nhau với n.

Ví dụ: nhập 12 thì in ra 4.

Kiểm tra: nhập 1000000000000.

Xem đáp số

400000000000

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Chia hết cho 2 hoặc 3 nhưng không chia hết cho 5

Nhập n (n ≤ 10¹⁸). Đếm các số từ 1 đến n chia hết cho 2 hoặc chia hết cho 3, nhưng không chia hết cho 5.

Ví dụ: nhập 100 thì in ra 54.

Kiểm tra: nhập 10000.

Xem đáp số

5334

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 21. Đúng k lá thư đúng phong bì

Bỏ ngẫu nhiên n lá thư vào n phong bì đã ghi địa chỉ (mỗi phong bì một lá, n ≤ 20). Có bao nhiêu cách để đúng k lá thư vào đúng phong bì của nó (0 ≤ k ≤ n)?

Ví dụ: nhập 3 1 thì in ra 3.

Kiểm tra: nhập 6 2.

Xem đáp số

135

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 22. Đội có cả nam và nữ

Lớp có a bạn nam và b bạn nữ (a + b ≤ 60). Chọn một đội k bạn (k ≤ a + b) có ít nhất một nam và ít nhất một nữ. Có bao nhiêu cách?

Ví dụ: nhập 2 2 2 thì in ra 4.

Kiểm tra: nhập 10 8 5.

Xem đáp số

8260

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.