问题
12cm应该是能够构成直角三角形的最小(以cm为单位的)整数周长,它只能有一种直角三角形组合。但是还有其它能组成直角三角形整数周长的组合。
12 cm: (3,4,5) 24 cm: (6,8,10) 30 cm: (5,12,13) 36 cm: (9,12,15) 40 cm: (8,15,17) 48 cm: (12,16,20)
相对地,有些整数长度无法形成任何直角三角形,例如20cm。而有些整数长度的周长,例如120cm则可以组成刚好3种直角三角形。
120 cm: (30,40,50), (20,48,52), (24,45,51)
那么请问,当整数长度的周长L ≤ 1,500,000时,有多少种情况只能组成1种直角三角形?
* 传送门
分析
又见毕达哥拉斯三元组,在《问题9》和《问题39》中都已经详细探讨过。只要将《问题39》中的答案3稍微改一改、就可以得到答案。这里列出要用到的推论:
首先,三元组表达为:\(a^2+b^2=c^2 \Rightarrow (a,b,c) = (2t\cdot mn, t\cdot (m^2-n^2), t\cdot (m^2+n^2))\),其中,它们有如下性质:\(n \lt m, n \perp m, t\geq 1, m\in \mathbb{Z}^+, n\in \mathbb{Z}^+, t\in \mathbb{Z}^+\)。
而周长L和m、n的关系为:\(a+b+c = 2t\cdot m\cdot (m+n) = L\)。这里可以推出:\(m \leq \lfloor \sqrt{\frac{L}{2}} \rfloor \)。
遍历的时候,只需要考虑\((m+n)\)是奇数的单边情况。
《问题39》的解答过程是从L计算出可能的m和n;而这里则相反,只要知道了m的范围,就可以遍历出各种m和n的情况,只要周长L少于等于1,500,000,都会累计数量。
答案
// answer: tripplets inverse
const start = Date.now()
function gcd(a, b) {
if (b == 0)
return a
else
return gcd(b, a%b)
}
const counts = {}
function incr_count(L) {
if (L in counts)
++counts[L]
else
counts[L] = 1
}
const is_odd = (num) => num%2 == 1
const limit = 1500000
const max_m = Math.floor(Math.sqrt(limit/2))
for (let m = 2; m <= max_m; ++m)
for (let n = 1; n < m; ++n) {
const m_plus_n = m+n
if (is_odd(m_plus_n) && gcd(n, m) == 1) {
const base_L = 2*m*m_plus_n
for (let L = base_L; L <= limit; L += base_L)
incr_count(L)
}
}
let result = 0
for (const L in counts)
if (counts[L] == 1)
++result
alert(result + ', ' + (Date.now()-start) + 'ms')
打赏作者