ProjectEuler 309 Integer Ladders - 拼圖

※ 引述《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秒不到




--

--