====== 제곱수의 합 2 (More Huge) ======

===== 풀이 =====
  * 루비 문제 중에서는 풀이가 많이 있는 편이다. 출제자가 직접 쓴 풀이도 찾을수 있다.
  * 풀이는 [[ps:제곱수의 합]]를 참고.
  * 두 제곱수로 나누는 방법을 찾기 위해서, 가우스정수의 최대공약수를 이용해서 구하는 방식과, Hermite-Serret 알고리즘으로 구하는 방식이 있는데, 실행 시간은 거의 비슷했다.

===== 코드 =====
(다이아몬드 이상은 코드 생략)
  * Dependency: [[:ps:teflib:numtheory#prime_factorization|teflib.numtheory.prime_factorization]]

{{tag>BOJ ps:problems:boj:루비_4}}