시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB202790868253.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

1
25
2003
211
20007
0

예제 출력 1

1
3
48
7
738
W3sicHJvYmxlbV9pZCI6IjM5MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI3N2NcdWFkZjhcdWI3OTFcdWM4ZmNcdWM3NTggXHViMTI0IFx1YzgxY1x1YWNmMVx1YzIxOCBcdWM4MTVcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWIyOTQgXHViOWNlXHVjNTQ0XHVjNTdjIDRcdWFjMWNcdWM3NTggXHVjODFjXHVhY2YxXHVjMjE4XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1Yzc3NFx1Yjg2MFx1Yzc0NCA8YSBocmVmPVwiaHR0cDpcL1wvZW4ud2lraXBlZGlhLm9yZ1wvd2lraVwvTGFncmFuZ2UlMjdzX2ZvdXItc3F1YXJlX3RoZW9yZW1cIj5cdWI3N2NcdWFkZjhcdWI3OTFcdWM4ZmNcdWM3NTggXHViMTI0IFx1YzgxY1x1YWNmMVx1YzIxOCBcdWM4MTVcdWI5YWM8XC9hPlx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWI5YWNcdWIyOTQgXHVjODcwXHVjODFjXHVkNTA0XHViOGU4XHVjNzc0IFx1Yjc3Y1x1YWRmOFx1Yjc5MVx1YzhmY1x1YWMwMCAxNzcwXHViMTQ0XHVjNWQwIFx1Yzk5ZFx1YmE4NVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHViMjk0IFx1Yzc3NCBcdWM3NzRcdWI4NjBcdWM3NDQgXHVjOTlkXHViYTg1XHVkNTU4XHVhYzcwXHViMDk4IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM3NzRcdWI4NjBcdWM3NDQgXHViYzFjXHVhY2FjXHVkNTYwIFx1ZDU0NFx1YzY5NFx1YjI5NCBcdWM1YzZcdWFjZTAsIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyA0XHVhYzFjIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM1OTFcdWM3NTggXHVjODFjXHVhY2YxXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBuXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NjAgXHViNTRjIFx1YzgxY1x1YWNmMVx1YzIxOFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHViYzE0XHViMDBjXHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViODVjIFx1YmNmOFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIDM8c3VwPjI8XC9zdXA+ICsgNDxzdXA+MjxcL3N1cD4gXHVhY2ZjIDQ8c3VwPjI8XC9zdXA+ICsgMzxzdXA+MjxcL3N1cD5cdWIyOTQgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Tlx1Yzc3NCAyNVx1Yzc3YyBcdWI1NGMgNFx1YWMxYyBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODFjXHVhY2YxXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IDE8c3VwPjI8XC9zdXA+ICsgMjxzdXA+MjxcL3N1cD4gKyAyPHN1cD4yPFwvc3VwPiArIDQ8c3VwPjI8XC9zdXA+LCAzPHN1cD4yPFwvc3VwPiArIDQ8c3VwPjI8XC9zdXA+LCA1PHN1cD4yPFwvc3VwPiBcdWM3NzRcdWI4MDdcdWFjOGMgM1x1YWMwMFx1YzljMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWNkNWNcdWIzMDAgMjU1XHVjOTA0XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IDI8c3VwPjE1PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc4OFx1YWNlMCwgXHVjNzg1XHViODI1IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgblx1Yzc0NCBcdWI5Y2VcdWM1NDRcdWM1N2MgNFx1YWMxY1x1Yzc1OCBcdWM4MWNcdWFjZjFcdWMyMThcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM5MzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMYWdyYW5nZVx1MjAxOXMgRm91ci1TcXVhcmUgVGhlb3JlbSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGZhY3QgdGhhdCBhbnkgcG9zaXRpdmUgaW50ZWdlciBoYXMgYSByZXByZXNlbnRhdGlvbiBhcyB0aGUgc3VtIG9mIGF0IG1vc3QgZm91ciBwb3NpdGl2ZSBzcXVhcmVzIChpLmUuIHNxdWFyZXMgb2YgcG9zaXRpdmUgaW50ZWdlcnMpIGlzIGtub3duIGFzIExhZ3JhbmdlJnJzcXVvO3MgRm91ci1TcXVhcmUgVGhlb3JlbS4gVGhlIFx1ZmIwMXJzdCBwdWJsaXNoZWQgcHJvb2Ygb2YgdGhlIHRoZW9yZW0gd2FzIGdpdmVuIGJ5IEpvc2VwaC1Mb3VpcyBMYWdyYW5nZSBpbiAxNzcwLiBZb3VyIG1pc3Npb24gaG93ZXZlciBpcyBub3QgdG8gZXhwbGFpbiB0aGUgb3JpZ2luYWwgcHJvb2Ygbm9yIHRvIGRpc2NvdmVyIGEgbmV3IHByb29mIGJ1dCB0byBzaG93IHRoYXQgdGhlIHRoZW9yZW0gaG9sZHMgZm9yIHNvbWUgc3BlY2lcdWZiMDFjIG51bWJlcnMgYnkgY291bnRpbmcgaG93IG1hbnkgc3VjaCBwb3NzaWJsZSByZXByZXNlbnRhdGlvbnMgdGhlcmUgYXJlLjxcL3A+XHJcblxyXG48cD5Gb3IgYSBnaXZlbiBwb3NpdGl2ZSBpbnRlZ2VyIG4sIHlvdSBzaG91bGQgcmVwb3J0IHRoZSBudW1iZXIgb2YgYWxsIHJlcHJlc2VudGF0aW9ucyBvZiBuIGFzIHRoZSBzdW0gb2YgYXQgbW9zdCBmb3VyIHBvc2l0aXZlIHNxdWFyZXMuIFRoZSBvcmRlciBvZiBhZGRpdGlvbiBkb2VzIG5vdCBtYXR0ZXIsIGUuZy4geW91IHNob3VsZCBjb25zaWRlciA0PHN1cD4yPFwvc3VwPiArIDM8c3VwPjI8XC9zdXA+IGFuZCAzPHN1cD4yPFwvc3VwPiArIDQ8c3VwPjI8XC9zdXA+IGFyZSB0aGUgc2FtZSByZXByZXNlbnRhdGlvbi48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGxldCZyc3F1bztzIGNoZWNrIHRoZSBjYXNlIG9mIDI1LiBUaGlzIGludGVnZXIgaGFzIGp1c3QgdGhyZWUgcmVwcmVzZW50YXRpb25zIDE8c3VwPjI8XC9zdXA+KzI8c3VwPjI8XC9zdXA+KzI8c3VwPjI8XC9zdXA+KzQ8c3VwPjI8XC9zdXA+LCAzPHN1cD4yPFwvc3VwPiArIDQ8c3VwPjI8XC9zdXA+LCBhbmQgNTxzdXA+MjxcL3N1cD4uIFRodXMgeW91IHNob3VsZCByZXBvcnQgMyBpbiB0aGlzIGNhc2UuIEJlIGNhcmVmdWwgbm90IHRvIGNvdW50IDQ8c3VwPjI8XC9zdXA+ICsgMzxzdXA+MjxcL3N1cD4gYW5kIDM8c3VwPjI8XC9zdXA+ICsgNDxzdXA+MjxcL3N1cD4gc2VwYXJhdGVseS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBpcyBjb21wb3NlZCBvZiBhdCBtb3N0IDI1NSBsaW5lcywgZWFjaCBjb250YWluaW5nIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgbGVzcyB0aGFuIDI8c3VwPjE1PFwvc3VwPiwgZm9sbG93ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgemVyby4gVGhlIGxhc3QgbGluZSBpcyBub3QgYSBwYXJ0IG9mIHRoZSBpbnB1dCBkYXRhLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGJlIGNvbXBvc2VkIG9mIGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlci4gTm8gb3RoZXIgY2hhcmFjdGVycyBzaG91bGQgYXBwZWFyIGluIHRoZSBvdXRwdXQuPFwvcD5cclxuXHJcbjxwPlRoZSBvdXRwdXQgaW50ZWdlciBjb3JyZXNwb25kaW5nIHRvIHRoZSBpbnB1dCBpbnRlZ2VyIG4gaXMgdGhlIG51bWJlciBvZiBhbGwgcmVwcmVzZW50YXRpb25zIG9mIG4gYXMgdGhlIHN1bSBvZiBhdCBtb3N0IGZvdXIgcG9zaXRpdmUgc3F1YXJlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2003 in Aizu B번