欧拉计划 发表于 2016-9-15 01:29:41

题目176：共享直角边的直角三角形

Right-angled triangles that share a cathetus

The four right-angled triangles with sides (9,12,15), (12,16,20), (5,12,13) and (12,35,37) all have one of the shorter sides (catheti) equal to 12. It can be shown that no other integer sided right-angled triangle exists with one of the catheti equal to 12.

Find the smallest integer that can be the length of a cathetus of exactly 47547 different integer sided right-angled triangles.

题目：

(9,12,15)，(12,16,20)，(5,12,13) 和 (12,35,37)这四个直角三角形都有一条直角边等于 12。可以证明不存在其他某直角边等于 12 的整数边长直角三角形。

求恰好可以作为 47547 个整数边直角三角形的直角边边长的最小整数。



永恒的蓝色梦想 发表于 2021-1-10 10:51:35

本帖最后由 永恒的蓝色梦想 于 2021-1-10 15:14 编辑

考察一个完全平方数可以以多少种方式写成完全平方数的差

瓦屋青衣 发表于 2021-3-31 00:58:00

import time
import math

timeStart = time.time()

n = 47547*2+1

def primeLis(n:int) -> list:
    ans = []
    lis =
    for x in range(2, n+1):
      if lis:
            continue
      ans.append(x)
      for i in range(2*x, n+1, x):
            lis = 1
    return ans

def primeDivisor(n:int) -> dict:
    ans = []
    plis = primeLis(int(n**0.5))
    x = n
    while True:
      if x == 1:
            break
      for p in plis:
            while x%p == 0:
                x //= p
                ans.append(p)
    ans.sort(reverse=True)
    return ans

plis = primeLis(int(math.log2(n)))
pdLis = primeDivisor(n)
ans = 2
for p, r in zip(plis, pdLis):
    ans *= p**(r//2)

print(ans)

print(f'time used: {time.time() - timeStart: .3f} s')

guosl 发表于 2022-10-20 11:21:24

这个题目是不能死做的。要用数学的方式来解。我们只要找一个数使得它的平方有2x47547+1的因子。
2x47547+1=95095=5x7x11x13x19。
如果一个数n=p1^a1x...pk^ak，则其n^2有(2a1+1)x...x(2ak+1)个因子。
那么最小的可能数就是2^9x3^6x5^5x7^3x11^2或2x(2^9x3^6x5^5x7^3x11^2)。因为后者把2带到每个因数分解也行。
最后检验得：2x(2^9x3^6x5^5x7^3x11^2)=96818198400000是解。
页: [1]
查看完整版本: 题目176：共享直角边的直角三角形