백준 3933 : 라그랑주의 네 제곱수 정리

라그랑주의 네 제곱수 정리 성공출처다국어분류

한국어   www.acmicpc.net/problem/3933

3933번: 라그랑주의 네 제곱수 정리

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

1232

518

397

57.122%

문제

양의 정수는 많아야 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

#include <iostream>
#include <math.h>
using namespace std;

int main(void)
{
	int num, end, cnt;

	num = 1;
	cnt = 0;
	while (num != 0)
	{
		cin >> num;
		if (num == 0)
			break;

		cnt = 0;
		end = sqrt(num);
		for (int i = 1; i <= end; i++)
		{
			if (i * i == num)
			{
				cnt++;
				continue ; // necessary
			}
			for (int j = i; j <= end; j++)
			{
				if (i * i + j * j == num)
				{
					cnt++;
					break; // necessary
				}
				else if (i * i + j * j > num)
					break;
				for (int k = j; k <= end; k++)
				{
					if (i * i + j * j + k * k == num)
					{
						cnt++;
						break;//necessary
					}
					else if (i * i + j * j + k * k > num)
						break;
					for (int l = k; l <= end; l++)
					{
						if (i * i + j * j + k * k + l * l == num)
						{
							cnt++;
							break;
						}
						else if (i * i + j * j + k * k + l * l > num)
							break;
					}

				}
			}
		}
		cout << cnt << "\n";
	}
}