1281.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1281 on 2006-02-17 at 08:07:03 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 32768;
const int N_MAX = 182;

int squ[N_MAX], psq[MAX];

int enumer(int, int, int);

int main()
{
	int i, n;

	for(i = 0; i < N_MAX; i++) squ[i] = i * i, psq[squ[i]] = 1;
	while(scanf("%d", &n) != EOF && n != 0)
		printf("%d\n", enumer(n, 1, 0));
	
	return 0;
}

int enumer(int n, int b, int step)
{
	if(step == 3) return psq[n];
	else {
		int i, total = psq[n], o = upper_bound(squ, squ+N_MAX, n/2) - squ;
		for(i = b; i < o; i++)
			total += enumer(n-squ[i], i, step+1);
		return total;
	}
}