시간 제한메모리 제한제출정답맞힌 사람정답 비율
5.555 초 555 MB279945432.335%

문제

제곱수를 가지고 놀던 상근이는 음이 아닌 정수 $n$을 네 제곱수의 합으로 나타내는 경우의 수보다 다섯 제곱수의 합으로 나타내는 경우의 수가 훨씬 더 많다는 것을 깨달았다.

예를 들어, $n = 1$일 때 네 제곱수의 합으로 나타내는 경우는

$$ \begin{align*} 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$을 네 제곱수의 합으로 나타내는 경우의 수"와 "음이 아닌 정수 $n$을 다섯 제곱수의 합으로 나타내는 경우의 수"는 각각

$$ r_{4}(n) = \left\vert \{ \left( a_{1}, a_{2}, a_{3}, a_{4} \right) \in \mathbb{Z}^{4} \ : \ n = {a_{1}}^2 + {a_{2}}^2 + {a_{3}}^2 + {a_{4}}^2\} \right\vert $$

$$ r_{5}(n) = \left\vert \{ \left( a_{1}, a_{2}, a_{3}, a_{4}, a_{5} \right) \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$을 네 제곱수의 합으로 나타내는 경우의 수와 다섯 제곱수의 합으로 나타내는 경우의 수를 구해주자!

입력

첫째 줄에 정수 $n$이 주어진다. ($0 \leq n \leq 10^{10}$)

출력

첫째 줄에 $n$을 네 제곱수의 합으로 나타내는 경우의 수를, 둘째 줄에 $n$을 다섯 제곱수의 합으로 나타내는 경우의 수를 출력한다.

예제 입력 1

100

예제 출력 1

744
10890

예제 입력 2

1000000

예제 출력 2

468744
11057207850

예제 입력 3

10000000000

예제 출력 3

292968744
11059865643913290

출처