라그랑쥐 수 timer 1s memory 128MB

양의 정수는 많아야 4 개의 제곱수의 합으로 표현가능하다는 것이 1770 년에 Joseph-Louis Lagrange 에 의해서 처음 발표되었다. 이는 Lagrange's Four-Square 이론으로 알려져 있다.

우리가 관심있는 것은 양의 정수가 주어질 때 제곱수의 합으로 만들 수 있는 종류가 몇 개가 되는 지를 구하는 것이 문제이다. 제곱수는 최대 4 개까지 사용가능한다. 단 42 + 32 과 32 + 42 은 같은 표현으로 본다.

예를 들어 n 이 25 인 경우 3가지 표현이 가능하다.

1² + 2² + 2² + 4²

3² + 4²

5²

물론 0 이 되는 답은 없다.