https://www.acmicpc.net/problem/1699

모든 수는 네 제곱수의 합으로 표현가능함이 증명되어있습니다.(아마 라마누잔이 증명했을 것입니다.) 그렇기 때문에 우리는 주어진 수가 제곱수인지 / 두 제곱수의 합으로 표현가능한지 / 세 제곱수의 합으로 표현가능한지만 판단하면 됩니다. N이 제법 크기 때문에 제곱수인지 / 두 제곱수의 합으로 표현가능한지를 미리 배열에 값을 저장해두어 상수시간에 꺼내쓸 수 있도록 했습니다.

https://github.com/encrypted-def/BOJ/blob/master/1699.cpp