포함-배제 원리의 기초 개념

포함-배제 원리는 여러 집합의 합집합 크기를 정확히 계산하기 위한 수학적 방법이다. 단순히 각 집합의 원소 수를 더하면 중복이 발생하므로, 이를 체계적으로 보정하여 중복 없이 전체 개수를 구한다.

예를 들어 세 개의 집합 \( A, B, C \)가 있을 때, 그들의 합집합의 크기는 다음과 같이 표현된다:

\[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \]

이 식은 일반화되어 \( n \)개의 집합에 대해 다음과 같은 형태로 확장된다:

\[ \left| \bigcup_{i=1}^{n} A_i \right| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap \cdots \cap A_n| \]

즉, 홀수 개의 집합 교집합은 더하고, 짝수 개는 빼는 방식으로 번갈아 적용한다.

부분집합 생성과 비트 마스크 기법

\( n \)개 원소로 구성된 집합의 모든 부분집합은 총 \( 2^n \)개 존재한다. 이 성질을 이용해, 각 부분집합을 길이 \( n \)인 이진수로 표현할 수 있다. 여기서 각 비트는 해당 인덱스의 원소가 부분집합에 포함되는지를 나타낸다 (1: 포함, 0: 미포함).

예를 들어, 원소가 3개인 집합의 경우, 숫자 5는 이진수로 101이며, 이는 첫 번째와 세 번째 원소만 선택한 부분집합을 의미한다.

비트 연산을 통한 효율적 구현

모든 가능한 부분집합을 순회하기 위해 0부터 \( 2^n - 1 \)까지의 정수를 반복하며, 각 수를 비트 표현으로 해석한다. 특정 비트 위치 \( j \)가 활성화되었는지 확인하려면, 다음과 같은 비트 연산을 사용한다:

if (mask & (1 << j)) { /* j번째 원소 포함 */ }

이 방식은 문자열 변환 없이 빠르게 상태를 검사할 수 있어 알고리즘 구현에 매우 유리하다.

실전 예제: 특정 수의 배수 개수 세기

문제: 주어진 자연수 \( N \) 이하에서 2, 3, 5, 7, 11의 배수가 되는 수는 몇 개인가?

해결 전략: 각 소수 조합에 대해 최소공배수를 계산하고, 포함-배제 원리를 적용하여 중복을 제거하면서 합산한다.

예를 들어, 2와 3의 공배수는 6의 배수이며, 이들은 단순히 2의 배수와 3의 배수를 더했을 때 두 번 세어지므로 한 번 빼야 한다. 마찬가지로 2,3,5의 공배수는 다시 더해야 하며, 이 규칙이 반복된다.

C++ 코드 구현

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

int main() {
    vector<int> primes = {2, 3, 5, 7, 11};
    int N;
    cin >> N;
    
    long long totalCount = 0;
    int setSize = primes.size();
    
    // 모든 부분집합을 비트 마스크로 순회
    for (int bitmask = 1; bitmask < (1 << setSize); ++bitmask) {
        long long lcm = 1;
        int selectedCount = 0;
        
        for (int i = 0; i < setSize; ++i) {
            if (bitmask & (1 << i)) {
                lcm *= primes[i];
                ++selectedCount;
            }
        }
        
        // 포함-배제 원리 적용: 홀수 개면 더하고, 짝수 개면 뺀다
        if (selectedCount % 2 == 1) {
            totalCount += N / lcm;
        } else {
            totalCount -= N / lcm;
        }
    }
    
    cout << totalCount << endl;
    return 0;
}

이 프로그램은 모든 가능한 소수 조합을 비트 마스크로 탐색하고, 각 조합의 최소공배수를 기준으로 \( N \) 이하의 배수 개수를 계산하여 최종 결과를 도출한다.