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)에 다 된다
코드
(다이아몬드 이상은 코드 첨부 생략)
ps/problems/boj/5051.txt · 마지막으로 수정됨: 2021/02/18 15:27 저자 teferi
토론