다섯 제곱수의 합
시간 제한5.555초메모리 제한555 MB
0 이상 10^10 이하의 정수 n을 제곱수 네 개의 합과 다섯 개의 합으로 나타내는 방법의 수를 구합니다.
문제
제곱수를 가지고 놀던 상근이는 음이 아닌 정수 을 네 제곱수의 합으로 나타내는 경우의 수보다 다섯 제곱수의 합으로 나타내는 경우의 수가 훨씬 더 많다는 것을 깨달았다.
예를 들어, 일 때 네 제곱수의 합으로 나타내는 경우는
1 &= 1^2 + 0^2 + 0^2 + 0^2 \\ 1 &= {(-1)}^2 + 0^2 + 0^2 + 0^2 \\ 1 &= 0^2 + 1^2 + 0^2 + 0^2 \\ 1 &= 0^2 + {(-1)}^2 + 0^2 + 0^2 \\ 1 &= 0^2 + 0^2 + 1^2 + 0^2 \\ 1 &= 0^2 + 0^2 + {(-1)}^2 + 0^2 \\ 1 &= 0^2 + 0^2 + 0^2 + 1^2 \\ 1 &= 0^2 + 0^2 + 0^2 + {(-1)}^2 \end{align\*} $$ 으로 총 $8$가지이고, 다섯 제곱수의 합으로 나타내는 경우는 $$ \begin{align\*} 1 &= 1^2 + 0^2 + 0^2 + 0^2 + 0^2 \\ 1 &= {(-1)}^2 + 0^2 + 0^2 + 0^2 + 0^2 \\ 1 &= 0^2 + 1^2 + 0^2 + 0^2 + 0^2 \\ 1 &= 0^2 + {(-1)}^2 + 0^2 + 0^2 + 0^2 \\ 1 &= 0^2 + 0^2 + 1^2 + 0^2 + 0^2 \\ 1 &= 0^2 + 0^2 + {(-1)}^2 + 0^2 + 0^2 \\ 1 &= 0^2 + 0^2 + 0^2 + 1^2 + 0^2 \\ 1 &= 0^2 + 0^2 + 0^2 + {(-1)}^2 + 0^2 \\ 1 &= 0^2 + 0^2 + 0^2 + 0^2 + 1^2 \\ 1 &= 0^2 + 0^2 + 0^2 + 0^2 + {(-1)}^2 \end{align\*} $$ 으로 총 $10$가지이다. 엄밀하게 말해서, 음이 아닌 정수 $n$을 네 제곱수의 합으로 나타내는 경우의 수와 다섯 제곱수의 합으로 나타내는 경우의 수는 각각 다음과 같다. $$ r_{4}(n) = \left\vert \{ (a_1, a_2, a_3, a_4) \in \mathbb{Z}^4 : n = a_1^2 + a_2^2 + a_3^2 + a_4^2 \} \right\vert $$ $$ r_{5}(n) = \left\vert \{ (a_1, a_2, a_3, a_4, a_5) \in \mathbb{Z}^5 : n = a_1^2 + a_2^2 + a_3^2 + a_4^2 + a_5^2 \} \right\vert $$ 흥미를 느낀 상근이는 작은 $n$에 대해 경우의 수를 세어 표로 정리했다. | $n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | $r_{4}(n)$ | $1$ | $8$ | $24$ | $32$ | $24$ | $48$ | $96$ | $64$ | $24$ | $104$ | $144$ | | $r_{5}(n)$ | $1$ | $10$ | $40$ | $80$ | $90$ | $112$ | $240$ | $320$ | $200$ | $250$ | $560$ | 손으로 일일이 세다 지친 상근이를 위해, $n$이 주어지면 $n$을 네 제곱수의 합으로 나타내는 경우의 수와 다섯 제곱수의 합으로 나타내는 경우의 수를 구하는 프로그램을 만들어 보자.입력
첫째 줄에 정수 이 주어진다. ()
출력
첫째 줄에 을 네 제곱수의 합으로 나타내는 경우의 수를, 둘째 줄에 을 다섯 제곱수의 합으로 나타내는 경우의 수를 출력한다.