[BOJ][Python] 백준 28383번 - 다섯 제곱수의 합

문제 링크: https://www.acmicpc.net/problem/28383

---

문제 풀이

소인수분해, 정수론

 

네 제곱수의 합의 가짓수를 구하는 방법은 Jacobi's four-square theorem를 이용하면 된다.

간략하게 설명하면 $r_4(n)$이 $n$의 네 제곱수의 합의 가짓수를 구하는 함수인데,

$n$이 홀수라면 $8\sigma(n)$를 구하면 되고, $n$이 짝수라면 $ n = 2^{k}m$으로 나타낼 때, $24\sigma(m)$을 구하면 된다.

당연하겠지만 $\sigma(n)$를 구하기 위해서 소인수분해가 들어간다. $n = p_1^{q_1}p_2^{q_2}p_3^{q_3}\cdots p_k^{q_k}$으로 나타내면 $\prod_{i=1}^k \frac{p_i^{q_i + 1} - 1}{p_i - 1}$으로 구하면 되기 때문이다.

이렇게 구했다면 네 제곱수의 합의 가짓수는 구해진거고, 문제는 다섯 제곱수의 합의 가짓수를 구해야하는데 조금만 생각해보자.

$t = 0$부터 시작해서 $n \geq t$를 만족할 때까지 $1$씩 점점 더하면서 $r_4(n-t^{2})$을 구하면 된다. $t = 0$일 때를 제외하면 양수, 음수가 있으니 모두 고려하면 $r_5(n) = r_4(n) + 2\sum_{\substack{t=1 \\ t^2 \leq n}} r_4(n - t^2)$를 계산하면 된다.

 

시간제한이 5.555초이다보니 폴라드 로가 아닌 일반적인 소인수분해로도 풀어지긴 한다. 물론 시간 퍼포먼스는 5배 가량 차이나지만... 따라서 코드도 일반적인 소인수분해 코드를 올림.

 

코드