백준 17436 <소수의 배수> Python

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

---

포함 배제의 원리 문제입니다.

 

포함 배제의 원리는 여러 집합의 합집합의 원소의 개수를 구할 때 교집합을 처리하는 방법 이라고 생각해도 될 것 같습니다.

결론적으로 모든 집합의 합집합의 원소의 수는

 

모든 집합의 수를 모두 더하고

모든 2 개의 교집합의 수를 빼고

모든 3 개의 교집합의 수를 더하고

...

모든 2n 개의 교집합의 수를 빼고

모든 2n+1 개의 교집합의 수를 더하고

...

 

이 됩니다.

---

import sys
from itertools import combinations
from math import prod

input = sys.stdin.readline


def solution(N, M, primes):
    # 총 카운트
    total_cnt = 0
    # 소수 정렬
    primes = sorted(primes)
    # 조합 수 순회
    for i in range(1, N+1):
        # 조합 순회
        for comb in combinations(primes, i):
            # 배수의 수
            cnt = M//prod(comb)
            # 계산
            total_cnt += cnt if i%2 else -cnt
    
    print(total_cnt)


# 입력
N, M = map(int, input().strip().split())
primes = list(map(int, input().strip().split()))

solution(N, M, primes)