Count right-angled triangles with integer sides and given hypotenuse

user_14790634 0
Viewed 145

We are given a number N representing the hypotenuse of a right-angled triangle. The problem is how many right-angled triangles exist with integer sides and the given hypotenuse.

input: T number of tests and in every next T lines an integer as N

limitations: 1<N<10^9 and 1<T<100

sample input:

   3
   4
   5
   25

output:

   0
   1
   2

Note:i have an idea. from math we know every Pythagorean triple can represent like this:

      k*(m^2+n^2,2mn,m^2-n^2)

so for every N we should find all k,m,n st:k*(m^2+n^2)=N i have written this code:

from math import isqrt

def is_square(i):
    return i ==  isqrt(i)**2

def sub(n,k):
    ans=0
    i=1
    i2=i*i
    while 2*i2 < n:
        if is_square(n-i2) and (n-2*i2)*k not in a:
            ans+=1
            a.add(k*(2*i*isqrt(n-i2)))
            a.add(k*(n-2*i2))

        i=i+1
        i2=i*i
    return ans

def solve():
    n=int(input())
    ans=0
    for i in range(2,isqrt(n)+1):
        if n%i==0 :
            if not is_square(i):
                ans+=sub(n//i,i)
            if not is_square(n//i):
                ans+=sub(i,n//i)
    print(ans+sub(n,1))
a=set()
T=int(input())
for _ in range(T):
    a.clear()
    solve()

but time complexity (i guess) is O(N) or O(N* sqrt(N)) and can't pass time limit

math algorithm
1 Answers

We can use the counting procedure described in Wikipedia, we just need to subtract a couple of counts in certain cases, and take advantage of the factor arrangement of a squared number. O(sqrt n).

The code in the function, f, below was accepted by the online judge link you posted: https://quera.org/problemset/147639/

Python code equating your solution with that adaptation:

from math import sqrt

def isqrt(n):
  return int(sqrt(n))

def is_square(i):
    return i ==  isqrt(i)**2

def sub(n,k):
    ans=0
    i=1
    i2=i*i
    while 2*i2 < n:
        if is_square(n-i2) and (n-2*i2)*k not in a:
            ans+=1
            a.add(k*(2*i*isqrt(n-i2)))
            a.add(k*(n-2*i2))

        i=i+1
        i2=i*i
    return ans

def solve(n):
    ans=0
    for i in range(2,isqrt(n)+1):
        if n%i==0 :
            if not is_square(i):
                ans+=sub(n//i,i)
            if not is_square(n//i):
                ans+=sub(i,n//i)
    return ans+sub(n,1)

def f(x):
  n = x
  fs = []
  sqrt_n = sqrt(n)

  while n > 1 and n % 2 == 0:
    n //= 2

  i = 3
  while n > 1 and i <= sqrt_n:
    f = 0
    while n % i == 0:
      f += 1
      n //= i
    if f > 0 and i % 4 == 1:
      fs.append(2 * f)
    i += 2

  if n > 1 and n % 4 == 1:
    fs.append(2)

  if not fs:
    return 0

  result = 4
  for f in fs:
    result *= f + 1

  result -= 4
  if x**2 % 2 == 0 and int(sqrt(x**2 // 2))**2 == x**2 // 2:
    result -= 4

  return result // 8

a = set()

for x in range(2, 500):
  a.clear()
  _x, _f = solve(x), f(x)
  if _x != _f:
    print(x, _x, _f)

print("Done")
user_20347870
Related