题目描述
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去，就正好可以表示为 4 个数的平方和。
比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 4 个数排序：
0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d为联合主键升序排列，最后输出第一个表示法。
输入描述
程序输入为一个正整数 N(N<5×10^6)。
输出描述
要求输出 4 个非负整数，按从小到大排序，中间用空格分开
输入输出样例
示例
输入
12
输出
0 2 2 2
思路：
暴力寻找每一个数，做适当的剪枝处理
代码：
1. import math 2. n=int(input()) 3. #确定边界，题目要求的数一定小于给定的数的开方 4. x=int((math.sqrt(n))) 5. 6. #创建一个平方列表，减少寻找第四个数的时间 7. pf = [i ** 2 for i in range(0, x)] 8. 9. def f(x): 10. #暴力搜索每一个数，进行可行性剪枝 11. for a in range(x+1): 12. flag=0 13. if a*a>n: 14. flag=1 15. for b in range(a,x+1): 16. if flag: 17. break 18. if a*a+b*b>n: 19. flag=1 20. for c in range(b,x+1): 21. z=n-a*a-b*b-c*c 22. if z<0: 23. flag=1 24. break 25. else: 26. if z in list: 27. ans=sorted([a,b,c,int(math.sqrt(z))]) 28. return ans[0],ans[1],ans[2],ans[3] 29. a, b, c, d = f(x) 30. print(f"{a} {b} {c} {d}")
