====== 골드바흐 파티션 2 ======
  * [[ps:problems:boj:17103|골드바흐 파티션]]에서 T가 100에서 100,000으로 늘어난 문제.

===== 풀이 =====
  * [[ps:problems:boj:17103|골드바흐 파티션]]에서 했던 것처럼 쿼리마다 따로 파티션의 갯수를 찾으려 하지 말고, 그냥 한번에 모든 수에 대해서 파티션의 갯수를 미리 구해놓고, 쿼리마다 그 값을 출력하는 식으로 접근한다.
    * [[ps:problems:boj:17104|르모앙의 추측]]과 많이 비슷한 문제. 
  * 1,000,000보다 작은 소수 목록을 구해 놓고, [[ps:고속 푸리에 변환]]으로 [[ps:고속 푸리에 변환#all possible sums]]를 구하는 방법을 사용해서, 두 소수의 합으로 나올 수 있는 수들과 그 가짓수를 모두 구해놓는다. 그리고 각각의 쿼리에 대해서 이미 계산된 값을 O(1)에 출력하면 된다.
  * FFT로 구해진 값은, 두 소수의 순서만 다른 경우도 다른 것처럼 카운트해서 계산된 것이므로, [[ps:problems:boj:17103|골드바흐 파티션]]과 같은 방법으로 보정을 해줘야 한다.
  * 이렇게만 해도 [[ps:고속_푸리에_변환#한번_더_최적화_multiply_v20|fft.multiply v2.0]]을 쓰면 3000ms 정도에 통과가 가능하다. 그러나 [[ps:problems:boj:17104|르모앙의 추측]]과 거의 비슷한 문제임에도, 시간 제한을 1/4인 0.5초로 둔 것은 사소하게라도 좀 더 최적화를 하라는 의미일 듯 하니, 그 취지를 살려서 좀 더 최적화해보자. 모든 소수는 홀수이기 때문에, fft에 넘길 배열에서 짝수 인덱스에 해당하는 원소는 모두 0이 된다. 이것은 비효율적이니, 배열의 크기를 1,000,000이 아닌, 500,000으로 잡고, a[p]대신 a[p/2]의 값을 1로 저장해서 fft를 돌리면 시간을 절약할 수 있다.
  * 시간 복잡도는 소수 목록을 구하는 데에 O(nlogn), fft에 O(nlogn), t개의 결과를 출력하는데에 O(t). 총 O(nloglogn + t)이다.

===== 코드 =====
(다이아몬드 이상은 코드 첨부 생략)
  * Dependency: [[:ps:teflib:fft#multiply|teflib.fft.multiply]]

{{tag>BOJ ps:problems:boj:다이아몬드_5}}