포함 배제의 원리 (Inclusion-Exclusion Principle)

 

 

포함 배제의 원리 (Inclusion-Exclusion Principle)

포함 배제의 원리는 조합론에서 합집합의 크기를 구할 때 사용하는 공식이다.

 

 

그렇다면 합집합의 크기(원소의 개수)를 구하는 방법을 알아보자.

 

위 그림에서 합집합의 크기를 구하는 방법은 다음과 같다.

$$n(A\cup B\cup C) = n(A) + n(B) + n(C) - \{n(A\cap B) + n(B\cap C) + n(C\cap A)\} + n(A\cap B\cap C)$$

 

 

이를 일반화하면 다음과 같은 식이 성립한다.

 

전체집합의 모든 부분집합의 교집합의 원소를 더하거나 뺄 때, 부분집합의 수가 홀수라면 더하고, 짝수라면 뺀다.

 

문제

소수의 배수 (BOJ 17436)

https://www.acmicpc.net/problem/17436

17436번: 소수의 배수

코드

#include <iostream>
#include <cmath>
#include <vector>
typedef long long ll;
using namespace std;

ll n, m, tmp;
vector<ll> v;

int main() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v.push_back(tmp);
	}

	ll sum = 0;

    // 비트마스킹으로 부분집합 구하기
	for (int i = 1; i < (1<<n); i++) {
		ll lcm = 1;
		int odd = -1;
		for (int j = 0; j < n; j++) {
			if (i & (1<<j)) { 
				odd *= -1;
				lcm *= v[j];
			}
		}
		sum += odd * (m / lcm);
	}
	
	cout << sum;
	return 0;
}