르모앙의 추측

• 르모앙은 낯선 이름이지만, 그래도 대충 유명한 수학자여야 할것 같은데, 구글에서 '르모앙'을 검색하면 BOJ의 이 문제만 잔뜩 나온다.
  • 프랑스 뮤직비디오 감독이나, 벨기에 축구선수도 나오기는 한다.
• 대체 실존인물이긴 한건지, 그냥 문제에서 만든 가상의 인물은 아닌지 해서 다시 검색해봤는데, 실제로 있는 추측이긴 했다.

• 말을 헷갈리게 써놨지만, 짝수인 소수가 2뿐이므로, 짝수인 세미소수는 2*p형태밖에 없다.
• 그러면 p + 2*q = N 인 소수쌍 (p,q)의 갯수를 찾는 문제로, 골드바흐 파티션 2과 거의 비슷한 문제가 된다. 풀이도 거의 비슷하다.
• 우선 N이하의 모든 소수의 집합을 구하고, 거기에 2를 곱해서 모든 짝수 세미소수의 집합을 구한다. 그리고 고속 푸리에 변환 (Fast Fourier Transform, FFT)으로 all possible sums를 구하는 방법을 적용해서 모든 N에 대해 (p,q)의 갯수를 구해 놓은 뒤에, 각 쿼리에 대해서 계산된 값을 출력하기만 하면 된다.
• 소수 목록을 구하는 데에 O(nloglogn), FFT를 돌리는 데에 O(nlogn), t개의 쿼리를 처리하는 데에 O(t)가 걸리므로 총 시간 복잡도는 O(nlogn + t)
• 구현은 따로 안했지만, 소수와 세미소수를 그대로 리스트에 저장하지 말고, 2로 나눈 값을 저장하는 방식으로 처리하면 FFT를 돌릴 배열의 크기를 반으로 줄일수 있어서 속도를 크게 줄일 수 있다.

"""Solution code for "BOJ 17134. 르모앙의 추측".

- Problem link: https://www.acmicpc.net/problem/17134
- Solution link: http://www.teferi.net/ps/problems/boj/17134
"""

import sys
from teflib import fft
from teflib import numtheory


def main():
    T = int(sys.stdin.readline())
    N = [int(sys.stdin.readline()) for _ in range(T)]

    max_n = max(N)
    a = [0] * (max_n + 1)
    b = [0] * (max_n + 1)
    for p in numtheory.prime_list(max_n):
        a[p] = 1
        if 2 * p < max_n:
            b[2 * p] = 1

    c = fft.multiply(a, b)
    print(*(c[x] for x in N), sep='\n')


if __name__ == '__main__':
    main()

• Dependency: teflib.fft.multiply