四平方和（Python实现）

题目描述 四平方和定理，又称为拉格朗日定理： 每个正整数都可以表示为至多 4 个正整数的平方和。 如果把 0 包括进去，就正好可以表示为 4 个数的平方和。 比如： 5 = 02 + 02 + 12 + 22； 7 = 12 + 12 + 12 + 22； 对于一个给定的正整数，可能存在多种平方和的表示法。 要求你对 4 个数排序： 0≤a≤b≤c≤d 并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。 输入描述 程序输入为一个正整数N（N< 5 × 106）。 输出描述 要求输出4个非负整数，俺从小到大排序，中间用空格分开 输入输出样例 输入 12 输出 0 2 2 2 运行限制

最大运行时间：3s 最大运行内存：256

解题思路

1. 如果采用暴力法，利用循环，循环下界为0，上界不加以思考，以该数本身为上界，8个测试用例，其中一个测试用例超时。
2. 在方法1的基础上，修改上界，使其范围更小，一个数等于其余四个数的平方和，那么这四个数一定不会大于该数的平方，以此为上界进行尝试，结果如下。 解析：出现了一个段错误，思考后发现是因为循环上界定的不够精准，导致d变为了负数，如果在判断完全平方数函数中加以判断正负，结果得以改进。但仍然有一个测试用例超时。
3. 在上一个方法的基础上，再次尝试精准化限制上界。由于0≤a≤b≤c≤d限制，加上只输出联合主键升序排列的第一个表示，所以a的最大值只能和b,c,d相等，为(n/4)**0.5,其余字母同理。测试用例均通过。

def sqrt(n):
  return int(n ** 0.5)

def is_sqrt(n):
  if n < 0:
    return False
  sqrt_n = int(sqrt(n))
  if(sqrt_n ** 2 == n):
    return True
  else:
    return False
def num(n,i):
  return int((n/(5-i))**0.5)
def mathod(n):
  sqrt_n = sqrt(n)
  for a in range(num(n,1)):
    for b in range(num(n,2)):
      for c in range(num(n,3)):
        d = n - a * a - b * b - c * c
        if(is_sqrt(d)):
          return a,b,c,sqrt(d)

if __name__ == __main__:
  n = int(input())
  list_1 = mathod(n)
  list_2 = map(abs,list_1)
  print(*list_2)