테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 르모앙의 추측 ======
  * 르모앙은 낯선 이름이지만, 그래도 대충 유명한 수학자여야 할것 같은데, 구글에서 '르모앙'을 검색하면 BOJ의 이 문제만 잔뜩 나온다. 
    * 프랑스 뮤직비디오 감독이나, 벨기에 축구선수도 나오기는 한다.
  * 대체 실존인물이긴 한건지, 그냥 문제에서 만든 가상의 인물은 아닌지 해서 다시 검색해봤는데, [[https://en.wikipedia.org/wiki/Lemoine%27s_conjecture|실제로 있는 추측]]이긴 했다. 

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>
  * Dependency: [[:ps:teflib:fft#multiply|teflib.fft.multiply]]

{{tag>BOJ ps:problems:boj:플래티넘_1}}