P8635 [蓝桥杯 2016 省 AB] 四平方和【枚举+打表】

P8635 [蓝桥杯 2016 省 AB] 四平方和题目描述四平方和定理又称为拉格朗日定理每个正整数都可以表示为至多4 44个正整数的平方和。如果把0 00包括进去就正好可以表示为4 44个数的平方和。比如5 0 2 0 2 1 2 2 2 50^20^21^22^2502021222。7 1 2 1 2 1 2 2 2 71^21^21^22^2712121222。对于一个给定的正整数可能存在多种平方和的表示法。要求你对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(N5\times10^6)N(N5×106)。输出格式要求输出4 44个非负整数按从小到大排序中间用空格分开。输入输出样例 #1输入 #15输出 #10 0 1 2输入输出样例 #2输入 #212输出 #20 2 2 2输入输出样例 #3输入 #3773535输出 #31 1 267 838说明/提示时限 3 秒, 256M。蓝桥杯 2016 年第七届省赛蓝桥杯 2016 年省赛 A 组 H 题B 组 H 题。问题链接P8635 [蓝桥杯 2016 省 AB] 四平方和问题分析枚举问题打表c和d枚举a和b。参见参考链接。参考链接LQ0027 四平方和【枚举】题记略AC的C语言程序如下/* LQ0027 四平方和 */#includestdio.h#includestring.h#defineN5000000intC[N1],D[N1];voidinit(){memset(C,-1,sizeofC);for(intc0,c2;(c2c*c)N;c)for(intdc,b2;c2(b2d*d)N;d){inttc2b2;if(C[t]-1)C[t]c,D[t]d;}}voidsolve(intn){for(inta0,a2;(a2a*a)n;a)for(intba,b2;a2(b2b*b)n;b){intsumn-(a2b2);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;}