https://www.acmicpc.net/problem/17633
티어: 다이아몬드 3
로직
이 문제와 동일하지만 n의 범위가 작은 문제가 있습니다. (https://www.acmicpc.net/problem/1699)
여기선 n이 100000까지라 dp로 충분했었는데, 이 문제는 n의 범위가 심상치 않음 ( 10¹⁸... )
문제 지문에 문제를 푸는 결정적인 힌트가 나와있습니다. 라그랑주의 네 제곱수 정리인데, 이와 비슷하게 르장드르의 세 제곱수 정리, 페르마의 두 제곱수 정리 또한 존재합니다.
르장드르 세 제곱수 정리
https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem
꼴이 아닌 모든 정수 는 3개 이하의 제곱수의 합으로 표현 가능하다.
페르마 두 제곱수 정리
어떤 정수의 4n + 3 형태로 나타낼 수 있는 소인수가 모두 짝수 개라면 2개 이하의 제곱수의 합으로 표현 가능하다.
제곱수 1개로 표현할 수 있는지는 그 수가 제곱수인지 확인하면 되므로 간단히 구현 가능합니다.
큰 수의 소인수들을 모두 구해야 하므로 Pollard-Rho 소인수분해 알고리즘을 사용합니다.
'백준 & 알고리즘' 카테고리의 다른 글
| [파이썬] 백준 1351번 - 무한 수열 풀이 (0) | 2023.06.23 |
|---|---|
| [파이썬] 백준 3584번 - 가장 가까운 공통 조상 풀이 (0) | 2023.06.23 |
| [파이썬] 백준 28017번 - 게임을 클리어하자 풀이 (0) | 2023.06.11 |
| [파이썬] 백준 7501번 - Key 풀이 (0) | 2023.06.10 |
| [파이썬] 백준 16236번 - 아기 상어 풀이 (0) | 2023.05.31 |
