我的算法和在可能副本中找到的算法是O(n) 并且对于要求来说太慢了。
1 <= n <= 5*10^6
最佳答案
Euclid's formula告诉我们每个毕达哥拉斯三元组 (a, b, c) 都是由整数 k, n,m 组成的，其中 m>n
a=k*(m^2-n^2)
b=2*k*m*n
c=k*(m^2+n^2)
如果 C 可以表示为整数 k 与两个不相等整数平方和的乘积，则 C 是具有整数边的直角三角形的斜边。我们可以找到 C 的主要因素，并检查至少有一个因素是 Pythagorean prime形式为 4*p+1。需要 O(Sqrt(C)) 时间
关于algorithm - 确定 n 是否为具有整数边的三角形的斜边，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32935283/