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))
코드
(다이아몬드 이상은 코드 생략)
- Dependency: teflib.numtheory.prime_factorization
ps/problems/boj/17633.txt · 마지막으로 수정됨: 2023/03/20 14:54 저자 teferi
토론