포함 배제의 원리 (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/1..
