문제 링크: https://www.acmicpc.net/problem/17436

포함 배제의 원리를 이해하기에 적당한 문제입니다.

풀이

포함 배제의 원리?

포함 배제의 원리는 여러 개의 집합이 있을 때, 그 전체의 합집합의 크기를 구하는 방법을 말합니다.

이해하기

집합의 크기 = 집합에 속한 원소의 개수
집합 A의 크기는 $\vert A \vert$ 처럼 표기합니다.

간단하게 2개의 집합 A와 B가 있을 때를 먼저 생각해 봅시다. A와 B의 합집합의 크기는 다음과 같이 구할 수 있습니다.

$$\vert A \cup B \vert = \vert A \vert + \vert B \vert - \vert A \cap B \vert$$

이번엔 3개의 집합 A, B, C에 대해서 세 집합의 합집합에 속한 원소의 개수를 구해봅시다.

자료 출처: [조합론] 포함-배제의 원리(Inclusion-Exclusion Principle)
https://mango-juice.com/26

$$\vert A \cup B \cup C \vert = \vert A \vert + \vert B \vert + \vert C \vert - \vert A \cap B \vert - \vert B \cap C \vert - \vert C \cap A\vert + \vert A \cap B \cap C \vert$$

일반화

앞서 집합이 3개일때의 식을 풀어서 이해해보면 다음과 같습니다.

(1개 집합의 원소 개수의 합) - (2개 집합의 교집합의 원소 개수의 합) + (3개 집합의 교집합의 원소 개수의 합)

집합이 $N$개일 때도 크게 다르지 않습니다. 집합이 짝수 개 사용되었다면 빼고, 홀수 개 사용되었다면 더해주면 됩니다. 식으로 나타내면 다음과 같습니다.

$$\vert \bigcup_{i = 1}^{n} A_{i} \vert = \sum_{I \subset U} (-1)^{\vert I \vert + 1} \vert \bigcap_{i \in I} A_{i} \vert$$

한가지 재밌는 점은, $N$개 집합의 교집합의 크기를 합집합으로 구할 때도 같은 형태의 식이 사용됩니다.

$$\vert \bigcap_{i = 1}^{n} A_{i} \vert = \sum_{I \subset U} (-1)^{\vert I \vert + 1} \vert \bigcup_{i \in I} A_{i} \vert$$

조합 구하기

이 문제는 입력으로 주어진 $N$개의 소수들에 대해, $1 \dots M$의 수들 중 전체 소수 중 적어도 하나로 나누어지는 수의 개수를 찾는 문제입니다.

각 소수로 나누어 떨어지는 수들의 모음을 각 집합이라 생각해 봅시다.

간단한 예시를 먼저 들어보면, 1부터 10까지의 수 중 3으로 나누어 떨어지는 수의 개수는 $10 \div 3$으로 구할 수 있습니다. 이를 확장해, $1 \dots M$의 수들 중 임의의 수 $K$로 나누어 떨어지는 수의 개수는 $M \div K$입니다. 이를 어떤 수 $K$로 나누어 떨어지는 수의 집합의 크기로 생각할 수 있습니다.

포함 배제의 원리를 적용하기 위해서는, 교집합의 크기를 정의해야 합니다. 임의의 두 소수 $x, y$가 있을 때,
$M$ 이하의 자연수들 중 $x$로 나누어 떨어지는 수의 집합을 $X$, 소수 $y$로 나누어 떨어지는 수의 집합을 $Y$라고 하면

$$\vert X \cap Y \vert = M \div (x \times y)$가 됩니다.

교집합의 크기를 구하는 방법을 알았으니, 이제 포함 배제의 원리를 적용해 봅시다.

from itertools import combinations
from functools import reduce

N, M = map(int, input().split())
primes = list(map(int, input().split()))

res = 0
for i in range(1, N + 1):
    for comb in combinations(primes, i):
        base = reduce(lambda e, s: e * s, comb)
        cnt = M // base
        res += (-1) ** (i & 2 + 1) * cnt

• Python3에서, itertools모듈의 combinations는 주어진 배열의 원소들 중 $n$개를 순서 무관하게 선택하는 모든 경우의 수를 가지는 반복자(iterator) 입니다.
• Python3에서, functools모듈의 reduce는 주어진 배열의 원소를 매개변수로 받은 함수를 통해 합칩니다. 자세한 설명은 함수형 프로그래밍의 reduce에 대해 찾아보세요 😉

위 코드는 $1 \dots N$의 값을 가지는 $i$에 대해, $N$개의 소수 중 순서 무관하게 $i$개를 고르는 경우의 교집합의 크기를 통해 전체 합집합의 크기를 계산합니다.

각 경우의 교집합의 크기는 cnt변수에 저장되며, 최종 결과값인 포함 배제의 원리의 식에 따라 res에 더하거나 뺍니다.

전체 코드

from itertools import combinations
from functools import reduce

input = open(0).readline
N, M = map(int, input().split())
primes = list(map(int, input().split()))

res = 0
for i in range(1, N + 1):
    for comb in combinations(primes, i):
        base = reduce(lambda e, s: e * s, comb)
        cnt = M // base
        if i % 2: # Substract if odd
            res += cnt
        else: # Add if even
            res -= cnt

print(res)