题目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 个整数边直角三角形的直角边边长的最小整数。

永恒的蓝色梦想

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

瓦屋青衣

import time
import math

timeStart = time.time()

n = 47547*2+1

def primeLis(n:int) -> list:
    ans = []
    lis = [0 for _ in range(n+1)]
    for x in range(2, n+1):
        if lis[x]:
            continue
        ans.append(x)
        for i in range(2*x, n+1, x):
            lis[i] = 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

这个题目是不能死做的。要用数学的方式来解。我们只要找一个数使得它的平方有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是解。