[BOJ] 17436. 소수의 배수

Problem

BOJ 17436. 소수의 배수

$N$개의 소수와 자연수 $M$이 주어진다. $M$ 이하의 자연수 중에서 $N$개의 소수 중 적어도 하나로 나누어 떨어지는 수의 개수를 구하시오.

• $1 \le N \le 10$
• $1 \le M \le 10^{12}$
• 소수는 $100$ 이하

Input:
2 10
2 3

Output:
7

(Explanation: 2, 3, 4, 6, 8, 9, 10. Total 7 numbers divisible by 2 or 3.)

---

Initial Thought (Failed)

가장 단순한 방법은 $1$부터 $M$까지 모든 수를 확인하는 것입니다 (Brute Force).

• 시간 복잡도: $O(M)$
• $M \le 10^{12}$이므로, 일일이 확인하면 약 30,000년이 걸릴 수도 있습니다. 무조건 수학적 접근이 필요합니다.

---

Key Insight

집합의 합집합의 크기를 구하는 포함-배제의 원리 (Inclusion-Exclusion Principle)를 사용해야 합니다.

\(|A \cup B| = |A| + |B| - |A \cap B|\) \(|A \cup B \cup C| = (|A| + |B| + |C|) - (|A \cap B| + |A \cap C| + |B \cap C|) + (|A \cap B \cap C|)\)

즉,

1. 하나의 소수로 나누어 떨어지는 개수는 더하고,
2. 두 소수의 곱(LCM)으로 나누어 떨어지는 개수는 빼고,
3. 세 소수의 곱으로 나누어 떨어지는 개수는 더하고… 를 반복하면 됩니다.

---

Step-by-Step Analysis

$N=3$, 소수 ${2, 3, 5}$, $M=30$일 때:

graph TD
    S0["Start: Total = 0"]
    subgraph "Iteration 1: Size 1 (Add)"
        A1["+ M//2"] --> A2["+ M//3"] --> A3["+ M//5"]
    end
    subgraph "Iteration 2: Size 2 (Subtract)"
        B1["- M//(2*3)"] --> B2["- M//(2*5)"] --> B3["- M//(3*5)"]
    end
    subgraph "Iteration 3: Size 3 (Add)"
        C1["+ M//(2*3*5)"]
    end
    S0 --> A1
    A3 --> B1
    B3 --> C1
    C1 --> F["Result"]
    style A1 fill:#90EE90
    style B1 fill:#ffaaaa
    style C1 fill:#90EE90

1. 조합 생성: $N=10$이므로 $2^{10}=1024$가지의 모든 부분집합을 만듭니다.
2. 부호 결정: 부분집합 크기가 홀수면 +, 짝수면 -.
3. 개수 합산: total += sign * (M // LCM)

---

Solution

import sys
import math
from itertools import combinations

input = sys.stdin.read
data = input().split()

# 입력 처리
N = int(data[0])
M = int(data[1])
primes = list(map(int, data[2:]))

def lcm(a, b):
    # a, b가 소수라면 단순히 a*b와 같지만, 일반적인 공식을 사용
    return a * b // math.gcd(a, b)
# end def

def solve():
    total_count = 0
    
    # 1개부터 N개까지 소수를 선택하는 모든 조합 생성
    for i in range(1, N + 1):
        for comb in combinations(primes, i):
            # 선택된 소수들의 최소공배수(LCM) 계산
            current_lcm = 1
            for p in comb:
                current_lcm = lcm(current_lcm, p)
                # 가지치기: LCM이 M을 넘으면 더 이상 볼 필요 없음
                if current_lcm > M:
                    break
                # end if
            # end for
            
            if current_lcm > M:
                continue
            # end if
            
            # 포함-배제: 홀수 개는 더하고, 짝수 개는 뺀다
            term = M // current_lcm
            if i % 2 == 1:
                total_count += term
            else:
                total_count -= term
            # end if
        # end for
    # end for
    
    print(total_count)
# end def

solve()

---

Complexity

• Time Complexity: $O(2^N \cdot N)$
  • $N$개의 소수로 만들 수 있는 모든 조합($2^N$)을 순회합니다.
  • $N=10$이므로 $2^{10} \approx 1000$번 반복하므로 충분히 빠릅니다.
• Space Complexity: $O(N)$
  • 조합 생성을 위한 재귀 스택 또는 메모리

---

Key Takeaways

Point	Description
Inclusion-Exclusion	합집합의 크기를 구할 때 중복을 처리하는 공식
Logic	홀수 개 집합은 더하고, 짝수 개 집합은 뺀다
Optimization	$M$을 넘는 LCM은 계산에서 제외하여 오버플로우 및 불필요한 연산 방지