洛谷 P1586 四方定理

题目描述

四方定理是众所周知的：任意一个正整数 $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视为一种方案。$

输入输出格式

输入格式：

第一行为正整数

输出格式：

对于每个正整数

输入输出样例

输入样例#1：

1
2003

输出样例#1：

48
思路：1.四重循环。
错因：输出没有换行。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int t,n,ans;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        ans=0;
        for(int ii=0;ii*ii<=n;ii++)
            for(int j=ii;ii*ii+j*j<=n;j++)
                for(int k=j;k*k+j*j+ii*ii<=n;k++){
                    int num=n-ii*ii-j*j-k*k;
                    int s=(int)sqrt(num);
                    if(s*s==num&&k<=s)
                        ans++;
                }
        cout<<ans<<endl;
    }
}

思路：2.dp可以列出状态转移方程f[i][j]=Σf[i-k*k][j-1];

#include<iostream>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,n,f[100000][5];
int main(){
    f[0][0]=1;
    for(int k=1;k*k<=32768;k++)
        for(int i=k*k;i<=32768;i++)
            for(int j=1;j<=4;j++)
                f[i][j]+=f[i-k*k][j-1];
    cin>>t;
    while(t--){
        cin>>n;
        cout<<f[n][1]+f[n][2]+f[n][3]+f[n][4]<<endl;
    }
}

细雨斜风作晓寒。淡烟疏柳媚晴滩。入淮清洛渐漫漫。雪沫乳花浮午盏，蓼茸蒿笋试春盘。人间有味是清欢。