洛谷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 视为一种方案。

输入输出格式

输入格式:

第一行为正整数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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P3953 逛公园(dp 拓扑排序)

首先不难想到一个思路,\(f[i][j]\)表示到第\(i\)个节点,与最短路之差长度为\(j\)的路径的方案数

12330
来自专栏数据结构与算法

51nod 1135 原根(原根)

那么预处理出\(P - 1\)的所有的质因数\(p_1, p_2 \dots p_k\),暴力判断一下,如果$\exists i, a^{\frac{P - 1...

11130
来自专栏数据结构与算法

洛谷P1501 [国家集训队]Tree II(LCT)

20000
来自专栏数据结构与算法

洛谷P2522 [HAOI2011]Problem b(莫比乌斯反演)

题目描述 对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数。 ...

34750
来自专栏数据结构与算法

agc015E - Mr.Aoki Incubator(dp)

平面上有$n$个点,每个点都有一个位置$x_i$,和向右的速度$v_i$ 现在要求你对其中的一些点进行染色,当一个点被染色后,在无限距离内与它相遇的点也会被染...

13220
来自专栏ACM小冰成长之路

51Nod-1638-字符串重组

ACM模版 描述 ? 题解 仔细分析这个问题两个串儿的结构,首先将第一个串通过 ii 和 jj 拆解成三部分,i+1∼j−1i + 1 \sim j - 1 作...

26190
来自专栏计算机视觉与深度学习基础

Codeforces 468B

很好的一道集合关系的题目,我比赛时用的是dfs,后来看到有人用并查集。 两种方法本质是一样的,但后者实现起来更方便,代码更简练。 /**************...

236100
来自专栏函数式编程语言及工具

Scala Macros - 元编程 Metaprogramming with Def Macros

    Scala Macros对scala函数库编程人员来说是一项不可或缺的编程工具,可以通过它来解决一些用普通编程或者类层次编程(type level pr...

32090
来自专栏数据结构与算法

LOJ#6283. 数列分块入门 7

内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计讨论测试数据 题目描述 给出...

370140
来自专栏伪君子的梦呓

题解 ~ 输出三个数中的最大值 ~ C++ 做法

26250

扫码关注云+社区

领取腾讯云代金券