목차

제곱수의 합 2 (More Huge)
- 풀이
- 코드
토론

제곱수의 합 2 (More Huge)

ps
링크	acmicpc.net/…
출처	BOJ
문제 번호	17646
문제명	제곱수의 합 2 (More Huge)
레벨	루비 4
분류	정수론
시간복잡도	O(n^(1/4) * (logn)^(1/2))
인풋사이즈	n≤1,000,000,000,000,000,000
사용한 언어	Python 3.11
제출기록	34988KB / 120ms
최고기록	116ms
해결날짜	2023/03/19

풀이

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

코드

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

Dependency: teflib.numtheory.prime_factorization