P8635 [蓝桥杯 2016 省 AB] 四平方和【枚举+打表】
P8635 [蓝桥杯 2016 省 AB] 四平方和
题目描述
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多4 44个正整数的平方和。
如果把0 00包括进去，就正好可以表示为4 44个数的平方和。
比如：
5 = 0 2 + 0 2 + 1 2 + 2 2 5=0^2+0^2+1^2+2^25=02+02+12+22。
7 = 1 2 + 1 2 + 1 2 + 2 2 7=1^2+1^2+1^2+2^27=12+12+12+22。
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对4 44个数排序使得0 ≤ a ≤ b ≤ c ≤ d 0 \le a \le b \le c \le d0≤a≤b≤c≤d。
并对所有的可能表示法按a , b , c , d a,b,c,da,b,c,d为联合主键升序排列，最后输出第一个表示法。
输入格式
程序输入为一个正整数N ( N < 5 × 10 6 ) N(N<5\times10^6)N(N<5×106)。
输出格式
要求输出4 44个非负整数，按从小到大排序，中间用空格分开。
输入输出样例 #1
输入 #1
5输出 #1
0 0 1 2输入输出样例 #2
输入 #2
12输出 #2
0 2 2 2输入输出样例 #3
输入 #3
773535输出 #3
1 1 267 838说明/提示
时限 3 秒, 256M。蓝桥杯 2016 年第七届省赛
蓝桥杯 2016 年省赛 A 组 H 题（B 组 H 题）。
问题链接：P8635 [蓝桥杯 2016 省 AB] 四平方和
问题分析：枚举问题，打表c和d，枚举a和b。参见参考链接。
参考链接：LQ0027 四平方和【枚举】
题记：（略）
AC的C++语言程序如下：
/* LQ0027 四平方和 */#include<stdio.h>#include<string.h>#defineN5000000intC[N+1],D[N+1];voidinit(){memset(C,-1,sizeofC);for(intc=0,c2;(c2=c*c)<=N;c++)for(intd=c,b2;c2+(b2=d*d)<=N;d++){intt=c2+b2;if(C[t]==-1)C[t]=c,D[t]=d;}}voidsolve(intn){for(inta=0,a2;(a2=a*a)<=n;a++)for(intb=a,b2;a2+(b2=b*b)<=n;b++){intsum=n-(a2+b2);if(C[sum]!=-1){printf("%d %d %d %d\n",a,b,C[sum],D[sum]);return;}}return;}intmain(){init();intn;while(~scanf("%d",&n))solve(n);return0;}