Tìm bội số của 2 hoặc 3 hoặc 5 nhỏ hơn hoặc bằng N trong C++

Giới thiệu

Cho số N. Đếm số lượng số từ 1 đến N chia hết cho 2 hoặc 3 hoặc 5.

Ví dụ minh họa

Đầu vào

N = 7

Đầu ra

5

Giải thích

Các số 1..7: 1,2,3,4,5,6,7. Chia hết 2/3/5: 2,3,4,5,6 (5 số)

Phương pháp 1: Duyệt trực tiếp - O(N)

Kiểm tra từng số từ 1 đến N.

Phương pháp 2: Lý thuyết tập hợp - O(1)

Sử dụng nguyên lý bao hàm - loại trừ (Inclusion-Exclusion Principle):

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

|2| = N/2, |3| = N/3, |5| = N/5
|2∩3| = N/6, |2∩5| = N/10, |3∩5| = N/15
|2∩3∩5| = N/30

Triển khai bằng bitmask 3 bit (2³=8 trường hợp).

Chương trình minh họa

#include <bits/stdc++.h>
using namespace std;

int countMultiples(int n) {
    int values[] = {2, 3, 5};
    int count = 0;
    int bitMask = 1 << 3; // 8
    
    for (int i = 1; i < bitMask; i++) {
        int prod = 1;
        for (int j = 0; j < 3; j++)
            if (i & (1 << j))
                prod *= values[j];
        
        if (__builtin_popcount(i) % 2 == 1)
            count += n / prod;
        else
            count -= n / prod;
    }
    return count;
}

int main() {
    int n = 13;
    cout << "The number of multiples till " << n << " is " << countMultiples(n) << endl;
    return 0;
}

Đầu ra

The number of multiples till 13 is 9