122. 四平方和暴力枚举2016年蓝桥杯省赛 - 四平方和困难标签2016省赛暴力枚举题目描述四平方和定理又称拉格朗日定理每个正整数都可以表示为至多 4 个正整数的平方和。把 0 也算进去就正好可以表示为 4 个数的平方和比如502021222 5 0^2 0^2 1^2 2^2502021222712121222 7 1^2 1^2 1^2 2^2712121222一个正整数可能存在多种表示法。要求把 4 个数排序为0≤a≤b≤c≤d0 \le a \le b \le c \le d0≤a≤b≤c≤d并把所有表示法按a,b,c,da, b, c, da,b,c,d为联合主键升序排列输出排在最前面的那一组。输入描述一个正整数NNNN5000000N 5000000N5000000。输出描述4 个非负整数按从小到大排序中间用空格分开。输入输出样例示例 1输入5输出0 0 1 2示例 2输入12输出0 2 2 2示例 3输入773535输出1 1 267 838运行限制最大运行时间1s最大运行内存: 256M解题思路四个数要满足a2b2c2d2Na^2 b^2 c^2 d^2 Na2b2c2d2N并且0≤a≤b≤c≤d0 \le a \le b \le c \le d0≤a≤b≤c≤d输出字典序最小的那一组。直接四重循环枚举四个数太慢但注意到只要a,b,ca, b, ca,b,c定了ddd也就定了——剩下的部分必须是一个完全平方数。所以先算出d⌊N−a2−b2−c2⌋ d \left\lfloor \sqrt{N - a^2 - b^2 - c^2} \right\rfloord⌊N−a2−b2−c2​⌋再回头验证a2b2c2d2Na^2 b^2 c^2 d^2 Na2b2c2d2N就行。这样四重循环直接降成三重。把NNN看成一条长条就是a2a^2a2、b2b^2b2、c2c^2c2之外剩下的那截必须正好等于d2d^2d2否则这组(a,b,c)(a,b,c)(a,b,c)作废枚举时每一层都从上一个数开始b≥ab \ge ab≥a、c≥bc \ge bc≥b、d≥cd \ge cd≥c顺序既不重复也不遗漏同时用⋅\sqrt{\cdot}⋅​收紧每层的上界比如给定aaa后bbb最多取到N−a2\sqrt{N - a^2}N−a2​可以省掉大量不可能的取值。又因为a,b,c,da, b, c, da,b,c,d是从小到大一层层枚举的第一组满足等式的解恰好就是按a,b,c,da, b, c, da,b,c,d升序排在最前面的那组找到直接返回即可。以样例773535走一遍N 773535 a0 整个分支试遍无解 a1, b1 c1 … 266 剩余部分都不是完全平方数 c267 剩余 773535 - 1 - 1 - 267² 702244 d √702244 838且 838 ≥ 267 → 输出 1 1 267 838代码实现importmathdefhs(n):amint(math.sqrt(n))# a 最大值forainrange(am1):bmint(math.sqrt(n-a*a))# 给定a后b的最大值forbinrange(a,bm1):# 保证 a bcmint(math.sqrt(n-a*a-b*b))# 给定a和b后c的最大值forcinrange(b,cm1):# 保证 b ctn-a*a-b*b-c*c# 剩下的部分应等于 d^2dint(math.sqrt(t))# 计算difdcanda*ab*bc*cd*dn:returna,b,c,d nint(input())print( .join([str(x)forxinhs(n)]))复杂度分析时间复杂度O(N3/2)O(N^{3/2})O(N3/2)三层枚举a,b,ca, b, ca,b,c每层的上界都是N\sqrt{N}N​级别找到第一组解就返回实际往往远小于这个上界。空间复杂度O(1)O(1)O(1)只用了几个循环变量和临时变量。