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

정의

포함-배제 원리 (Inclusion-Exclusion Principle, PIE) 는 여러 집합의 합집합 크기를 교집합 항으로 표현하는 조합론 공식. 가장 간단한 형태:

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

N 개 집합으로 일반화하면 2^N 개 항의 교대 합:

|A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ |Aᵢ| - Σ |Aᵢ ∩ Aⱼ| + Σ |Aᵢ ∩ Aⱼ ∩ Aₖ| - ... + (-1)^(N+1) |A₁ ∩ ... ∩ Aₙ|

PS 에서는 “조건 k 개 중 적어도 하나 만족” 문제를 “모두 불만족 (여사건)” 으로 바꾸거나, 부분집합 순회 O(2^N) 로 정확한 카운팅.

문제 상황과 동기

“적어도 하나 만족” 또는 “정확히 k 개 조건 만족” 은 naive 로는 중복 세기가 매우 복잡.

• naive: 모든 경우를 직접 열거 → 중복 제거 불가 or O(N!)
• PIE: 부분집합별 교집합 계산 + 교대 합 → O(2^N)

핵심 통찰: “적어도 하나”를 집합 합으로 바꾸고, 교집합들을 부호 있게 더하면 정확히 한 번씩 카운트.

시각화

핵심 아이디어

2 집합

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

A + B 로 세면 A ∩ B 가 두 번 카운트되므로 한 번 빼야.

3 집합

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

• 1개 집합 항 (+)
• 2개 교집합 (-)
• 3개 교집합 (+)

일반 N 집합

|⋃ Aᵢ| = Σ_{S ⊆ {1..N}, S ≠ ∅} (-1)^(|S|+1) |⋂ᵢ∈S Aᵢ|

부분집합 S 마다 교집합 ⋂ᵢ∈S Aᵢ 계산, 크기가 홀수면 (+), 짝수면 (-).

총 2^N - 1 개 항. 각 항 계산이 O(1) 이면 전체 O(2^N).

여사건 트릭

|조건 아무것도 안 만족| = |Ω| - |⋃ Aᵢ|

“적어도 하나 만족” = Ω - (아무것도 안 만족). 때로 이쪽이 더 쉬움.

알고리즘

PIE(A[1..N]):
    total = 0
    for S ⊆ {1..N}, S ≠ ∅:            # 2^N - 1 개
        intersection_size = calc_intersection(S)
        sign = (-1)^(|S| + 1)
        total += sign * intersection_size
    return total

calc_intersection(S):
    # 문제별. 예: "집합 i 조건 모두 만족하는 개수"
    # 곱셈 원리, DP, 조합 등으로 계산
    ...

비트마스크 로 2^N 부분집합 순회.

구현

// 포함-배제: "1..n 중 소인수 p₁, p₂, ..., pₖ 중 적어도 하나로 나눠지는 수"
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k; cin >> n >> k;
  vector<int> primes(k);
  for (auto& p : primes) cin >> p;
  
  long long ans = 0;
  // 2^k 부분집합 순회 (공집합 제외)
  for (int mask = 1; mask < (1 << k); mask++) {
      long long product = 1;
      int cnt = 0;
      for (int i = 0; i < k; i++) {
          if (mask & (1 << i)) {
              product *= primes[i];
              cnt++;
          }
      }
      // product 의 배수 개수 = n / product
      long long term = n / product;
      if (cnt % 2 == 1) ans += term;   // 홀수면 +
      else ans -= term;                // 짝수면 -
  }
  cout << ans << "\n";
}

# itertools.combinations 로 부분집합 순회
from itertools import combinations
from math import prod
​
def inclusion_exclusion(n, primes):
  """1..n 중 primes 중 적어도 하나로 나눠지는 수"""
  total = 0
  k = len(primes)
  for size in range(1, k + 1):
      for subset in combinations(primes, size):
          product = prod(subset)
          term = n // product
          if size % 2 == 1:
              total += term
          else:
              total -= term
  return total
​
n, k = map(int, input().split())
primes = list(map(int, input().split()))
print(inclusion_exclusion(n, primes))

// 비트마스크 2^k 순회
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int k = Integer.parseInt(st.nextToken());
      int[] primes = new int[k];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < k; i++)
          primes[i] = Integer.parseInt(st.nextToken());
      
      long ans = 0;
      for (int mask = 1; mask < (1 << k); mask++) {
          long product = 1;
          int cnt = 0;
          for (int i = 0; i < k; i++) {
              if ((mask & (1 << i)) != 0) {
                  product *= primes[i];
                  cnt++;
              }
          }
          long term = n / product;
          if (cnt % 2 == 1) ans += term;
          else ans -= term;
      }
      System.out.println(ans);
  }
}

100 3
2 3 5

74

1000 2
7 11

220

복잡도

N ≤ 20 정도가 실용 한계. N=20 → 2^20 ≈ 10^6 항.

예제: 오일러 파이 (Euler’s Totient) 계산

φ(n): 1..n 중 gcd(k, n) = 1 인 k 개수

n = p₁^a₁ · p₂^a₂ · … · pₘ^aₘ 로 소인수분해. PIE 로:

φ(n) = n · (1 - 1/p₁) · (1 - 1/p₂) · ... · (1 - 1/pₘ)

“p 로 나눠지지 않는 수” 를 여사건 + PIE 로 계산한 결과.

구현 예시

long long euler_phi(long long n) {
    long long ans = n;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            ans -= ans / p;   // PIE 한 항
        }
    }
    if (n > 1) ans -= ans / n;
    return ans;
}

O(√n) 으로 PIE 를 암묵적으로 적용.

예제: 데랑주망 (Derangement)

D(n): 순열 중 고정점이 하나도 없는 개수

• Aᵢ = “i 가 고정점” 인 순열 집합
• |Aᵢ| = (n-1)!
• |Aᵢ ∩ Aⱼ| = (n-2)!
• …
• |⋃ Aᵢ| = Σ_{k=1}^n (-1)^(k+1) C(n, k) (n-k)!
• D(n) = n! - |⋃ Aᵢ|

최종 공식:

D(n) = n! · Σ_{k=0}^n (-1)^k / k!  ≈  n! / e

변형 / 활용

함정

1. 부호 실수

홀수 크기 (+), 짝수 크기 (-). 공식에서 (-1)^(|S|+1) 헷갈리지 않도록.

2. 공집합 처리

부분집합 순회시 공집합 (mask=0) 은 제외. ⋂∅ 는 정의 안 됨 or Ω.

3. 오버플로우

2^N 항의 누적 합. long long 필요.

4. 교집합 계산 실수

|Aᵢ ∩ Aⱼ| 가 독립이 아닐 때 곱셈 원리 쓰면 틀림. 문제 조건 잘 파악.

5. 시간 초과

N > 20 이면 2^N 불가능. 그 경우 DP, 메뫼이제이션, 또는 공식 유도 로 축약.

BOJ 연습 문제

참고

• 조합론
• 비트마스크 DP
• 정수론
• 오일러 파이 함수