勾股平铺

用$(a,b,c)$表示边长为整数的直角三角形的三边，可以将四个这样的三角形放在一起，使其构成边长为c的正方形。

例如，边长为$(3,4,5)$的三角形可以组成一个$5\time 5$的正方形，中间留有一个$1\times 1$的缺口。而这个$5\time 5$的正方形又恰好可以分割为25个$1\times 1$的小正方形。

若用$(5,12,13)$的三角形组成一个$13\time 13$的正方形，则中间的缺口将是$7\times 7$大小，就无法拼接成$13\times 13$的大正方形。

考虑边长为整数、且周长小于一亿的直角三角形，其中有多少个按上述方式拼接成大正方形后，中间留下的缺口也可以组成同样大小的大正方形？

本题难度:

解答

不妨设三边的长度为$a < b < c$，则容易看出缺口正方形的边长是$b-a$，因此只需找到能令$b-a$整除c的勾股数组即可。

用欧几里得算法生成周长不超过一亿的本原勾股数组，每个本原勾股数组$(a,b,c)$经过缩放可以生成$(10^8-1)/(a+b+c)$组解，从而不难计算出结果是$10057761$。

import math
r={}
for m in range(2,7072):
    for n in range(1-m%2,m,2):
        if math.gcd(m,n)==1:
            a,b,c=m*m-n*n,2*m*n,m*m+n*n
            a,b=min(a,b),max(a,b)
            if c%(b-a)==0 and (a,b,c) not in r:
                r[(a,b,c)]=100000000//(a+b+c)-(100000000%(a+b+c)==0)
print(sum(r[i] for i in r))