사용자 도구

사이트 도구


ps:problems:boj:17646

제곱수의 합 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 알고리즘으로 구하는 방식이 있는데, 실행 시간은 거의 비슷했다.

코드

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

토론

댓글을 입력하세요:
S T T Q L
 
ps/problems/boj/17646.txt · 마지막으로 수정됨: 2023/03/20 15:13 저자 teferi