推 puzzlez:感謝解答～ 11/07 07:43
→ utomaya:忘了講 m, n都會是整數, h才會是整數 不過應該不難證 11/14 16:11
※ 引述《babufong (嗶嗶)》之銘言：
: 309. Integer Ladders
: http://projecteuler.net/index.php?section=problems&id=309
: 在典型的"Crossing Ladders"(我不知道怎麼翻比較好)問題中
: 給定兩個對倒在狹窄但水平的街道牆上的梯子的長度為x,y
: 順便給你兩個梯子的交點到地面的高度為h
: 而我們被要求算出街道w有多狹窄
: （這兒有張圖 請點上列網址）
: 這兒這張圖 我們只消理會上述四個變項(x, y, h, w)為正整數的情況
: 舉個例子 如果x = 70 , y = 119 , h = 30 這樣我們可以算出w = 56
: 事實上啊 這三個變項x,y,h 考慮 0 < x < y < 200的情況
: 只存在五組組合(x, y, h)可以算出w 也為正整數解：
: (70, 119, 30), (74, 182, 21), (87, 105, 35), (100, 116, 35) 和 (119, 175, 40)
: 問題來了 如果我們考慮 0< x < y < 1000000
: 究竟存在多少組(x, y, h)可算出w 也為正整數解？
: -----------------------------------------------------------------------------
: 初次翻譯 請各位多多指教
底下有雷(不喜勿入)
假設長為x的梯子靠在牆上，其高度為m, 長為y的梯子靠在牆上，其高度為n
所以有兩個直角三角形
一個三邊長 w, m ,x (x為斜邊)
另一個三邊長 w, n ,y (y為斜邊)
w為其共用邊,
0<x<y< 10^6 故 0<m<n < 10^6
利用相似三角形的原理 一個簡單的計算可以得到h=m*n/(m+n)
w是共用邊 畢氏定理w*w+m*m=x*x
w*w=x*x-m*m=(x+m)(x-m)
w是整數, 且很顯然的 w<x
x<1,000,000 故 w也小於1,000,000
從1到1,000,000
用因式分解
對於某一w值(w為直角三角形之一邊) 搜出另一邊的所有可能值, 為一集合
任選此集合的2個元素 就是m,n值
測試m*n/(m+n)是否為整數?
解完
用C跑 大約10秒不到
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.70.181.249
※ 編輯: utomaya 來自: 219.70.181.249 (11/07 03:08)