시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 2027 | 908 | 682 | 53.659% |
양의 정수는 많아야 4개의 제곱수로 표현할 수 있다고 한다. 이 이론을 라그랑주의 네 제곱수 정리라고 한다. 이 정리는 조제프루이 라그랑주가 1770년에 증명했다.
우리는 이 이론을 증명하거나 새로운 이론을 발견할 필요는 없고, n이 주어졌을 때 4개 이하의 양의 제곱수의 합으로 n을 만들 수 있는 경우의 수를 구하려고 한다. 경우의 수를 구할 때 제곱수의 순서가 바뀌는 경우는 같은 경우로 본다. 따라서 32 + 42 과 42 + 32는 같은 경우이다.
N이 25일 때 4개 이하의 제곱수의 합으로 표현 할 수 있는 경우는 12 + 22 + 22 + 42, 32 + 42, 52 이렇게 3가지이다.
입력은 최대 255줄이다. 각 줄에는 215보다 작은 양의 정수가 하나씩 주어진다. 마지막 줄에는 0이 하나 있고, 입력 데이터가 아니다.
각 테스트 케이스에 대해서 입력으로 주어진 n을 많아야 4개의 제곱수로 나타내는 경우의 수를 출력한다.
1 25 2003 211 20007 0
1 3 48 7 738
ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2003 in Aizu B번