2021年广东工业大学第十五届文远知行杯程序设计竞赛（同步赛）C题 图墙+拉格朗日四平方数和定理

题意：

其实就是问一个数字能不能表示成5个正平方数的和.

题目：

链接：https://ac.nowcoder.com/acm/problem/220347
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

母牛哥有一桶油漆,把它用完可以给n平方米的墙涂上颜色.

母牛哥想要在墙上涂5个正方形(这些正方形的边长都是整数,单位是米),并且刚好把油漆用完.

母牛哥能做到吗?

输入描述:

第一行一个数字t(<=1000),表示测试样例数量

接下来t行,每行一个数字n(0<=n<=1000000),表示母牛哥的油漆可以涂多少平方米.

输出描述:

输出t行,对于每个输入.

如果母牛哥能够做到,就输出YES.

否则输出NO.

示例1

输入

2
4
55

输出

NO
YES

说明

4显然不能分解成5个正平方数,所以这桶油漆不能涂5个正方形.

55可以涂5个正方形,他们面积分别是1 4 9 16 25.

分析：

首先要知道拉格朗日四平方数和定理:
任意一个非负整数可以表示为四个平方数(0也是平方数)的和.
比如这样:
1=$1^2+0^2+0^2+0^2$
2=$1^2+1^2+0^2+0^2$
5=$2^2+1^2+0^2+0^2$
任意一个非负整数拆出来的平方数里面,可能有任意一个非负整数拆出来的平方数里面,可能有[0,4]个0.
有一个特殊的数字169,他分别可以表示成1,2,3,4个正平方数的和.
$169=13^2$
$169=12^2+5^2$
$169=12^2+4^2+3^2$
$169=10^2+8^2+2^2+1^2$
$169=12^2+4^2+2^2+2^2+1^2$
那么对于任意一个不小于169的整数的整数n,设m=n-169
这个m不小于0,分解成四个平方数,可能会含有0,1,2,3,4个0.
• 如果m分解出来的四个平方数中有四个正数,那么$n=m+13^2$
• 如果m分解出来的四个平方数中有三个正数,那么$n=m+12^2+5^2$
• 如果m分解出来的四个平方数中有两个正数,那么$n=m+12^2+4^2+3^2$
• 如果mm分解出来的四个平方数中有一个正数,那么$n=m+10^2+8^2+2^2+1^2$
• 如果m分解出来的四个平方数中有没有正数,那么$n=m+12^2+4^2+2^2+2^2+1^2$
所以任何不小于169的整数,都符合条件.

解法一：

对于小于169的整数,暴力打表发现以下几个数字不符合
0,1,2,3,4,6,7,9,10,12,15,18,33
所以如果输入是以上数字,直接NO
否则YES.

解法二：

对于小于200的数，递归判断查找这个数是否能表示成5个正平方数的和，
若能标记，输出YES，否则NO.
若大于200的数，直接YES.

AC代码：

#include<bits/stdc++.h> using namespace std; int n,dp[100],flag; void dfs(int a,int b){if(flag) return ;if(a==0&&b==0){flag=1;return ;}if(a==0||b<0)return ;for(int i=1;i<100;i++){dfs(a-1,b-dp[i]);} } int main(){int t;for(int i=1;i<100;i++)dp[i]=i*i;cin>>t;while(t--){cin>>n;flag=0;if(n>=200)cout<<"YES"<<endl;else{dfs(5,n);flag==1?cout<<"YES"<<endl:cout<<"NO"<<endl;}}return 0; }

总结

以上是生活随笔为你收集整理的2021年广东工业大学第十五届文远知行杯程序设计竞赛（同步赛）C题 图墙+拉格朗日四平方数和定理的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。