游客 注册 | 登录
中文 | En

3630 - 拉格朗日平方定理

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

事实上,任何正整数都可以表示成多个正整数的平方和被称为拉格朗日平方定理。定理的证明首次出版于1770年由约瑟夫·路易斯·拉格朗日。不过你的任务不是去解释原始证据来发现了新证据,但表明定理适用于一些特定的数据通过计算有多少这样的可能表示。
对于一个给定的正整数n,对于每个n你应该算出有多少种表示的情况，最多由四个整数的平方来表示。顺序并不重要,但你应该考虑4 ^ 2 + 3 ^ 2和3 ^ 2 + 4 ^ 2是相同的表示。
例如,让我们检查的情况下,25。这个整数刚刚三个表示1 ^ 2 + 2 ^ 2 + 2 ^ 2 + 4 ^ 2、3 ^ 2 + 4 ^ 2和5 ^ 2。因此在这种情况下你应该报告3。小心不要数4 ^ 2 + 3 ^ 2和3 ^ 2 + 4 ^ 2的区别。

题目输入

测试数据最多可以有255行，每组测试数据包含一个整数n，n<=2^15

题目输出

对于每组测试数据输出对应的解

输入/输出样例

输入格式

1
25
2003
211
20007

输出格式

1
3
48
7
738

C++解答

//拉格朗日平方定理
#include<bits/stdc++.h>
using namespace std;
#define N 40000
int main()
{
    //freopen("H:\\ACM_Problems\\TEST\\test.in","r",stdin);
    //freopen("H:\\ACM_Problems\\TEST\\test.out","w",stdout);
	int n;
	int d[1<<16][5];
	memset(d,0,sizeof(d));
	d[0][0]=1;
	for(int i=1;i*i<N;i++)  
		for(int j=1;j<5;j++)  
			for(int k=i*i;k<N;k++)  
				d[k][j]+=d[k-i*i][j-1];
	while(scanf("%d",&n)!=EOF&&n){
		printf("%d\n",d[n][1]+d[n][2]+d[n][3]+d[n][4]);
	}
	return 0;
}
请先登陆