[閒聊] Euler 139
https://projecteuler.net/problem=139
考慮直角三角形 (a, b, c)
用四個這樣的三角形以斜邊 c 當正方形的邊
中間會有一個正方形的洞
https://projecteuler.net/resources/images/0139.png
有些可以用若干個這樣大的洞拼成邊長 c 的正方形
問有多少周長在 10^8 以下的直角三角形符合上面的性質
雷
對直角三角形 (a, b, c) 且 a <= b <= c，中間的洞的長度是 b - a
假設令 d = b - a, 因為 d 要能整除 c, 令 c = kd
就會是 (a, a+d, kd)，且有
a^2 + (a+d)^2 = (kd)^2
在模 d 底下，就有
a^2 + a^2 = 0
所以顯然 d 可以整除 a，也就是所有邊都是 d 的倍數
也就是所有符合條件的三角形都有 b - a = 1 的 base case 再等比例放大
考慮 (a, a+1, c)，有
a^2 + (a+1)^2 = c^2
<=> 2a^2 + 2a + 1 - c^2 = 0
<=> (2a+1)^2 - 2c^2 = -1
又可以像前兩題一樣套用 negative Pell's equation
確定 a 能是整數即可，之後再等比例放大
例如 2a+1+c = s, 那相似的三角形就有 floor((10^8-1) / s) 個
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.77.61.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1693424836.A.1FE.html