[Python] 12944번 재미있는 숫자 놀이

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

---

 

25/09/14

 

 

전형적인 포함-배제 원리의 문제이다.

---

 

문제 접근 방식:

 

 

당신은 포함배제의 원리를 아는가?

 

$K$개 중 $m$개를 선택해서 $N$에 $m$개의 숫자의 $\text{lcm}$을 나눠준 값을 더하거나 빼주면 된다.

 

$m$이 홀수인 경우 더해주고, $m$이 짝수인 경우 빼주면 된다.

 

왜 그런지는 집합의 모습을 생각해보면 이해하기 쉬울 것이다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 12944번 재미있는 숫자 놀이
# 수학, 포함 배제의 원리
import sys
input = sys.stdin.readline
from math import lcm

ans = 0
N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(1, 1 << K):
    new_A = []
    for j in range(K):
        if i & (1 << j):
            new_A.append(A[j])
    a = lcm(*new_A)
    if i.bit_count() % 2 == 0:
        ans -= N // a
    else:
        ans += N // a
print(ans)