拉格朗日四平方定理相关有序元组计数代码超时优化求助

原代码核心问题 #

• 时间复杂度过高，四层嵌套循环的时间复杂度达到了*O(n²√n)*量级，n只要超过100就会出现明显超时
• 存在大量无效遍历，变量范围没有做针对性限制，且可以直接推导的a值仍然做了循环遍历
• 浮点运算多，容易出现精度误差同时降低运行效率

具体优化措施 #

1. 消除a的循环：通过两个条件联立推导可得：
   从条件2得 d = (e² - b - 3c) // 5（需满足整除且结果非负）
   代入条件1得 a² = n - b² - c² - d²，只需判断该值是否为非负完全平方数即可，无需遍历a
2. 缩小各变量遍历范围：
   • e的上限：由e² = b + 3c +5d ≤ √n +3√n +5√n =9√n，可得e最大为int((9*math.isqrt(n))**0.5) +1
   • c的上限：由3c ≤e²，可得c最大为e²//3，无需遍历到√n
   • b的上限：由b ≤ e² -3c，可得b最大为min(e² -3c, math.isqrt(n))，无需遍历到√n
3. 提前剪枝：计算得到d后先判断d*d > n - b*b - c*c，符合则直接跳过后续计算
4. 替换浮点运算为整数运算：全程使用Python内置math.isqrt做整数开平方，避免浮点精度问题同时提升速度

优化后代码 #

import math

n = int(input())
count = 0
max_b_c = math.isqrt(n)
max_e = int((9 * max_b_c) ** 0.5) + 1

for e in range(max_e + 1):
    e_sq = e * e
    max_c = min(e_sq // 3, max_b_c)
    for c in range(max_c + 1):
        rem_after_c = e_sq - 3 * c
        max_b = min(rem_after_c, max_b_c)
        for b in range(max_b + 1):
            rem = rem_after_c - b
            if rem < 0 or rem % 5 != 0:
                continue
            d = rem // 5
            sum_sq = b*b + c*c + d*d
            if sum_sq > n:
                continue
            a_sq = n - sum_sq
            a = math.isqrt(a_sq)
            if a * a == a_sq:
                count += 1
print(count)

内容的提问来源于stack exchange，提问作者Codi