[백준 17436] 소수의 배수 (python)

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

17436번: 소수의 배수

소수의 배수 문제

자연수 M 이하의 수 중에서 주어진 N개의 소수 중에 적어도 하나로 나누어 떨어지는 수의 개수를 세는 문제

포함배제의 원리에 대해 알고 있다면 어렵지 않게 해결 할 수 있다.

부분 집합을 찾는 과정에서 백트래킹을 이용했다.

📌문제 접근 포인트

1. 포함 배제의 원리에 대해 생각해보자. n(A∪B) = n(A) + n(B) - n(A∩B) 가 대표적인 예시로, 전체 집합의 수는 각각의 개수의 합과, 겹치는 부분을 빼고, 다시 겹치는 부분을 더해가는 형태로 이루어져 있다.
2. 형태를 생각하면 전체의 합 = 각각의 집합의 값 - 2개가 서로 겹치는 부분의 집합의 합 + 3개가 서로 겹치는 부분의 집합의 합 - 4개가 서로 겹치는 부분의 집합의 합 ... 형태로 이루어져 있다. 즉, 홀수 항에서 +, 짝수 항에서 -를 한다.
3. 소수로 나누는 부분에 대해서 서로 겹치는 집합은 결국 n개의 소수끼리의 곱을 의미한다. 소수끼리의 곱을 구해주기 위해서 모든 부분 집합을 찾아보자
4. 모든 부분 집합을 찾아서, 홀수일 때 +, 짝수일 때 -를 해주면서 계산하면 된다. 

⚙️내가 푼 정답코드

def find(a):
    global num, result
    if a == N :
        if not num : # 비었으면
            return # 끝
        
        temp = 1
        for i in range(len(num)): # 각 부분 집합의 곱
            temp *= num[i]
        
        #포함 배제의 원리
        if len(num) % 2 : # 홀수면
            result += M // temp # 더하고
        else : # 짝수면
            result -= M // temp # 빼고
        return
    
    num.append(x[a])
    find(a+1)
    num.pop()
    find(a+1)
    
import sys
N, M = map(int, sys.stdin.readline().split())
x = list(map(int, input().split()))
num = []
result = 0
find(0)
print(result)