Py3 C++利用Euclid公式達O(n)解Leetcode1925 Count Square Sum Triples

Py3 C++利用Euclid公式達O(n)解Leetcode 1925  Count Square Sum Triples

用數論方法解畢氏定理三角整數解個數，這應該算是Diophantine  Equation中最簡單的例題

[Py3解請進]

------

This solution uses number theory to find the number of triangular integer solutions to the Pythagorean equation. This should be considered the simplest example in the Diophantine Equation.

[codes on Leetcode]https://leetcode.com/problems/count-square-sum-triples/solutions/7399102/euclids-formula-binary-euclidean-algo-in-eeas/

class Solution:
    def countTriples(self, n: int) -> int:
        cnt=0
        nsqrt=int(sqrt(n))
        for s in range(2, nsqrt+1):
            for t in range((s&1)+1, s, 2):
                if gcd(s,t)!=1: continue
                c=s*s+t*t
                if c>n: break
                k=n//c
                cnt+=2*k
        return cnt