四方定理是众所周知的:任意一个正整数nn ,可以分解为不超过四个整数的平方和。例如:25=1^{2}+2^{2}+2^{2}+4^{2}25=12+22+22+42 ,当然还有其他的分解方案,25=4^{2}+3^{2}25=42+32 和25=5^{2}25=52 。给定的正整数nn ,编程统计它能分解的方案总数。注意:25=4^{2}+3^{2}25=42+32 和25=3^{2}+4^{2}25=32+42 视为一种方案。
输入格式:
第一行为正整数tt (t\le 100t≤100 ),接下来tt 行,每行一个正整数nn (n\le 32768n≤32768 )。
输出格式:
对于每个正整数nn ,输出方案总数。
输入样例#1
1
2003
输出样例#1:
48
$N^4$暴力可过
正解是背包dp[i][j]表示用i种平方数拼出j的方案数
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
const int MAXN=1e5+10;
int dp[5][MAXN];
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
dp[0][0]=1;
for(register int i=1;i<=200;i++)
for(register int j=1;j<=4;j++)
for(register int k=1;k<=32768;k++)
if(i*i<=k)
dp[j][k]+=dp[j-1][k-i*i];
int T;
scanf("%d",&T);
while(T--)
{
int a;
scanf("%d",&a);
printf("%d\n",dp[1][a]+dp[2][a]+dp[3][a]+dp[4][a]);
}
return 0;
}
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
const int MAXN=1e6+10;
int mul[MAXN],dp[MAXN];
int ans[MAXN];
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
int N=200;
for(int i=1;i<=N;i++) mul[i]=i*i;
for(int i=1;i<=N;i++) ans[ mul[i] ] ++;
for(int i=1;i<=N;i++)
for(int j=i;j<=N;j++)
ans[ mul[i]+mul[j] ] ++;
for(int i=1;i<=N;i++)
for(int j=i;j<=N;j++)
for(int k=j;k<=N;k++)
ans[ mul[i]+mul[j]+mul[k] ] ++;
for(int i=1;i<=N;i++)
for(int j=i;j<=N;j++)
for(int k=j;k<=N;k++)
for(int l=k;l<=N;l++)
ans[ mul[i]+mul[j]+mul[k]+mul[l] ]++;
int T;
scanf("%d",&T);
while(T--)
{
int a;
scanf("%d",&a);
printf("%d\n",ans[a]);
}
return 0;
}