algorithm - 计算具有整数边和给定斜边的直角三角形

Question

我们得到一个数字 N代表直角三角形的斜边。 问题是存在多少个具有整数边和给定斜边的直角三角形。

输入:T测试次数和接下来的 T 行中的整数 N

限制:1<N<10^9 and 1<T<100

示例输入:

   3
   4
   5
   25

输出:

   0
   1
   2

注意:我有一个想法。 从数学上我们知道每个毕达哥拉斯三元组都可以这样表示:

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

所以对于每个 N 我们应该找到所有 k,m,n st: k*(m^2+n^2)=N 我写了这段代码:

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()

但时间复杂度(我猜)是 O(N) or O(N* sqrt(N))并且不能超过时间限制

Answer 1

我们可以使用 Wikipedia 中描述的计数程序，我们只需要在某些情况下减去几个计数，并利用平方数的因子排列。 O(sqrt n).

下面函数中的代码f被您发布的在线判断链接接受:https://quera.org/problemset/147639/

将您的解决方案等同于该改编的 Python 代码:

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")