테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 피타고라스의 정리 ======

===== 풀이 =====
  * 결국 정리하면 a+b=x인 a,b,x의 갯수를 세는 문제라서, [[ps:고속 푸리에 변환]]으로 [[ps:고속 푸리에 변환#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)에 다 된다



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

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