題意：

其實就是問一個數字能不能表示成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题 图墙+拉格朗日四平方数和定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。