사용자 도구

사이트 도구


ps:problems:boj:17104

골드바흐 파티션 2

ps
링크https://www.acmicpc.net/problem/17104
출처BOJ
문제 번호17104
문제명골드바흐 파티션 2
레벨다이아몬드 5
분류

정수론, 고속 푸리에 변환

시간복잡도O(nlogn + t)
인풋사이즈n <= 1,000,000, t <= 100,000
사용한 언어Python
제출기록107200KB / 1580ms
최고기록1580ms
해결날짜2021/02/14

풀이

  • 골드바흐 파티션에서 했던 것처럼 쿼리마다 따로 파티션의 갯수를 찾으려 하지 말고, 그냥 한번에 모든 수에 대해서 파티션의 갯수를 미리 구해놓고, 쿼리마다 그 값을 출력하는 식으로 접근한다.
  • 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)이다.

코드

(다이아몬드 이상은 코드 첨부 생략)

토론

댓글을 입력하세요:
J L P N X
 
ps/problems/boj/17104.txt · 마지막으로 수정됨: 2021/03/31 14:15 저자 teferi