pku2042.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 43 行

#include <stdio.h>
#include <string.h>
#define SIZE 65537
int ans[SIZE][5];
int Ans[SIZE];

void init()
{
	int i, j, k;
	memset(ans, 0, sizeof(ans));
	for (i = 1; i <= 256; i++)
	{
		ans[i * i][0]++;
		for (j = 1; j < 4; j++)
		{
			for (k = 1; k < SIZE; k++)
			{
				if (i * i + k >= SIZE)
				{
					break;
				}
				ans[i * i + k][j] += ans[k][j - 1];
			}
		}
	}
	for (i = 0; i < SIZE; i++)
	{
		Ans[i] = ans[i][0] + ans[i][1] + ans[i][2] + ans[i][3];
	}
}

int main()
{
	int N;
	init();
	while (scanf("%d", &N) != -1 && N)
	{
		printf("%d\n", Ans[N]);
	}
	return 0;
}