골드바흐 파티션 2

• 골드바흐 파티션에서 T가 100에서 100,000으로 늘어난 문제.

• 골드바흐 파티션에서 했던 것처럼 쿼리마다 따로 파티션의 갯수를 찾으려 하지 말고, 그냥 한번에 모든 수에 대해서 파티션의 갯수를 미리 구해놓고, 쿼리마다 그 값을 출력하는 식으로 접근한다.
  • 르모앙의 추측과 많이 비슷한 문제.
• 1,000,000보다 작은 소수 목록을 구해 놓고, 고속 푸리에 변환 (Fast Fourier Transform, FFT)으로 all possible sums를 구하는 방법을 사용해서, 두 소수의 합으로 나올 수 있는 수들과 그 가짓수를 모두 구해놓는다. 그리고 각각의 쿼리에 대해서 이미 계산된 값을 O(1)에 출력하면 된다.
• FFT로 구해진 값은, 두 소수의 순서만 다른 경우도 다른 것처럼 카운트해서 계산된 것이므로, 골드바흐 파티션과 같은 방법으로 보정을 해줘야 한다.
• 이렇게만 해도 fft.multiply v2.0을 쓰면 3000ms 정도에 통과가 가능하다. 그러나 르모앙의 추측과 거의 비슷한 문제임에도, 시간 제한을 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: teflib.fft.multiply