목차

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

제곱수의 합 (More Huge)

ps
링크	acmicpc.net/…
출처	BOJ
문제 번호	17633
문제명	제곱수의 합 (More Huge)
레벨	다이아몬드 4
분류	정수론
시간복잡도	O(n^(1/4))
인풋사이즈	n<=1,000,000,000,000,000,000
사용한 언어	Python 3.11
제출기록	35760KB / 88ms
최고기록	88ms
해결날짜	2023/03/18

풀이

Four Squares과 제곱수의 합의 (많이) 어려운 버전
풀이는 제곱수의 합을 참고.
Four Squares의 코드와 다른점은, 2개의 제곱수의 합으로 표현 여부를 찾기 위해 페르마의 두 제곱수 정리를 사용했다는 부분. 이때 소인수분해를 하기 위해 Pollard's Rho방법을 사용했다.
총 시간복잡도는 O(n^(1/4))

코드

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

Dependency: teflib.numtheory.prime_factorization

BOJ, 다이아몬드 4