사용자 도구

사이트 도구


ps:problems:boj:5051

피타고라스의 정리

ps
링크acmicpc.net/…
출처BOJ
문제 번호5051
문제명피타고라스의 정리
레벨다이아몬드 5
분류

고속 푸리에 변환

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

풀이

  • 결국 정리하면 a+b=x인 a,b,x의 갯수를 세는 문제라서, 고속 푸리에 변환 (Fast Fourier Transform, FFT)으로 All possible sums를 계산하는 기본 패턴으로 해결가능 하다.
  • (a^2 % n) + (b^2 % n) = (c^2 % n) 이거나 (a^2 % n) + (b^2 % n) = (c^2 % n) + n 인 a,b,c의 갯수를 구하는 문제가 된다. 크기 n짜리 리스트를 만들어서 l[k]에 a^2 % n == k가 되는 a의 갯수를 저장한다. 이거는 1 ~ n-1까지의 모든 a에 대해서 실제로 a^2%n을 구해보면서 갯수를 세면 된다. 이렇게 만든 l을 FFT를 써서 제곱하면 (a^2 % n) + (b^2 % n) = x 인 (a,b)의 갯수를 얻을 수 있다. 그리고 (c^2 % n) = x 인 c의 갯수가 l에 담겨있으므로 이값을 곱해주면 (a^2 % n) + (b^2 % n) = (c^2 % n) = x 인 (a,b,c)의 갯수를 얻는다. (c^2 % n) + n 에 대해서도 마찬가지로 하면 된다.
  • 푸리에 변환에만 O(nlogn)이 걸리고, 나머지 과정은 다 O(n)에 다 된다

코드

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

토론

댓글을 입력하세요:
P F D U A
 
ps/problems/boj/5051.txt · 마지막으로 수정됨: 2021/02/18 15:27 저자 teferi