洛谷P1586 四方定理

2018-02-07 20:14:39来源:cnblogs.com作者:自为风月马前卒人点击

分享

题目描述

四方定理是众所周知的:任意一个正整数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: 复制
12003
输出样例#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;}
 

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台