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 알고리즘으로 구하는 방식이 있는데, 실행 시간은 거의 비슷했다.
코드
(다이아몬드 이상은 코드 생략)
- Dependency: teflib.numtheory.prime_factorization
ps/problems/boj/17646.txt · 마지막으로 수정됨: 2023/03/20 15:13 저자 teferi
토론