如何高效计算共享同一斜边的毕达哥拉斯三角形数量

• 不需要获取各三角形的具体边长参数，只需要尽可能快地得到计数结果

最初的暴力遍历实现如下，运行速度过慢：

from math import sqrt
def hypotenuse(n):
    count = 0
    hypotenuse = n
    for x in range(1, int(n / (sqrt(2))) + 1):
        y = (((hypotenuse * hypotenuse) - (x * x)) ** 0.5)
        if y % 1 == 0:
            count += 1
                 
    return count 

优化说明：已经将去重逻辑的数据结构从列表替换为集合（后续甚至完全移除了去重步骤），同时将遍历范围从(1, n)缩小为(1, int(n / sqrt(2)))，但运行速度仍然无法满足要求。

数论优化思路 #

暴力遍历的时间复杂度为O(n)，斜边值较大时运行效率极低，可以通过两平方和定理直接推导计数公式，将复杂度降到O(√n)的质因数分解级别：

1. 勾股数的斜边n，能构成的直角三角形个数仅和n的质因数中模4余1的质数有关，模4余3的质数、因子2都不影响最终计数
2. 对n做质因数分解，记所有模4余1的质因数的指数为a_i，则总三角形个数（不计边长顺序、边长为正整数）公式为：
   count = (所有(2*a_i +1)的乘积 - 1) // 2
3. 原理是数论中的两平方和表示计数规则，排除掉边长为0的无效解、正负值重复、x/y顺序重复后即可得到上述结果。

优化后代码 #

def count_hypotenuse_triangles(n):
    if n < 5:
        return 0
    product = 1
    # 移除所有因子2，不影响计数结果
    while n % 2 == 0:
        n = n // 2
    # 遍历所有奇质因数
    i = 3
    while i * i <= n:
        exp = 0
        while n % i == 0:
            exp += 1
            n = n // i
        # 仅模4余1的质因数参与乘积计算
        if i % 4 == 1:
            product *= 2 * exp + 1
        i += 2
    # 剩余未分解的部分是质数
    if n > 1 and n % 4 == 1:
        product *= 3
    return (product - 1) // 2

效果对比 #

• 当n=10^{6时，原暴力代码需要循环约70万次，涉及大量浮点开方运算，耗时百毫秒级；优化后代码仅需要循环到10}3量级，无需浮点运算，耗时微秒级
• 当n=10^{12时，原暴力代码完全无法在合理时间内出结果，优化后代码仅需要循环到10}6量级，几毫秒即可得到结果

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