사용자 도구

사이트 도구


ps:problems:boj:17633

제곱수의 합 (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))

코드

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

토론

댓글을 입력하세요:
P T S Y E
 
ps/problems/boj/17633.txt · 마지막으로 수정됨: 2023/03/20 14:54 저자 teferi