32647 골드바흐흑흙의 추측 (백준, python3)

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

골드 바흐 흑흙

시간 제한	메모리 제한
1초	1024MB

문제

혁준이의 친한 친구 골드바흐흑흙은 호기심이 아주 많다.

어느 날, 골드바흐흑흙이 혁준이에게 물었다. 중복되지 않는 A이상 B이하인 소수들의 합으로 K를 표현할 수 있는 경우의 수는 얼마나 될까?

혁준이는 다섯 살이라서 골드바흐흑흙의 질문에 답할 수가 없으므로, 여러분이 대신 구해주자.

고른 수들은 같고 순서만 다른 경우들은 하나의 경우로 처리한다. 예를 들어, {2, 3}과 {3, 2}는 같은 경우이다.

 

입력

첫 번째 줄에 양의 정수 A, B, K가 공백을 사이에 두고 주어진다. (1 ≤ A < B ≤ 5e7; B - A ≤ 300; 1 ≤ K ≤ 2e9)

 

출력

문제의 정답을 출력한다.

 

---

풀이

A와 B의 제한 조건을 잘 보면 B - A가 300 이하라는 특이한 부분이 있습니다. 이걸 생각해봤을 때 우리가 찾아야 하는 소수는 그리 많지 않습니다. 문제는 소수가 좀 크다는 것이죠. 그래서 만약 범위의 끝에 걸친 49,999,700에서 50,000,000까지의 소수를 에라토스테네스의 체로 찾는다고 생각해보면 사실 300만큼의 범위에서 소수를 찾는 것이 아니라 50,000,000까지의 소수를 다 찾는 것이 됩니다. 시간제한을 넘기는 것도 문제가 될 수 있고 메모리가 문제입니다. 소수를 찾는 특별한 다른 방법이 필요할 것 같습니다.

 

여기서 소수를 순차적으로 찾는 것이 아니라 특정 수가 소수인지 아닌지 빠르게 판별하는 방법이 필요합니다.

밀러-라빈 소수판별법(Miller-Rabin primality test)

정리해 놓았으니 자세한 건 위를 참고합니다.

 

밀러-라빈 소수판별법으로 A~B 범위의 소수를 빠르게 찾았습니다. 이제 K를 구성하는 0-1 배낭문제만 남았습니다. 근데 숫자가 좀 크니 저는 dict를 활용해 문제를 해결했습니다. A부터 B까지의 소수를 작은 것부터 확인해 구성할 수 있는 모든 수를 set에 포함시킵니다. 다음 소수 p를 확인할 때 set에 있는 수들에 p를 더해 새로운 수를 만들어보고, dict[p]에 경우의 수를 더해줍니다. 마지막으로 dict[k]가 있다면 dict[k]를 출력, 없다면 0을 출력합니다.

 

 

정답 코드

import sys
input = sys.stdin.readline

a, b, k = map(int, input().split())
prime = []

def fast_mod_power(a, b, m):
    ret = 1
    a %= m
    while b:
        if b & 1:
            ret *= a
            ret %= m
        b >>= 1
        a **= 2
        a %= m
    return ret

def miller_rabin(n, a):
    d = n - 1
    while d & 1 == 0:
        d >>= 1
    x = fast_mod_power(a, d, n)
    if x == 1 or x == n - 1:
        return True
    while d != n - 1:
        x = fast_mod_power(x, 2, n)
        d <<= 1
        if x == 1:
            return False
        elif x == n - 1:
            return True
    return False

def is_prime(k):
    if k in [2, 7, 61]:
        return True
    if k == 1 or k & 1 == 0:
        return False
    for t in [2, 7, 61]:
        if not miller_rabin(k, t):
            return False
    return True

for p in range(a, b + 1):
    if is_prime(p):
        prime.append(p)

conj = dict()
numbers = set()
sorted_list = [0]
conj[0] = 1
numbers.add(0)
for p in prime:
    new_num = set()
    for now in sorted_list:
        next = p + now
        if next > k: continue
        if next in conj: conj[next] += conj[now]
        else:
            conj[next] = conj[now]
            new_num.add(next)
    numbers.update(new_num)
    sorted_list = sorted(list(numbers), reverse = True)
if k in conj: print(conj[k])
else: print(0)