[中譯] ProjectEuler 370 Geometric triangles

[babufong (嗶嗶)]

370. Geometric triangles

http://projecteuler.net/problem=370


讓我們將 等比三角形 定義為有整數邊的三角形且 a ≦ b ≦ c

並形成一個等比數列，也就是說 b^2 = a * c


舉個例子來說，a = 144、b = 156、c = 169 就是個等比三角形。


而在周長≦ 10^6 的三角形中，共有 861805 個等比三角形。


請問在周長≦ 2.5 * 10^13 的範圍內有幾個等比三角形存在？

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 125.224.6.222
推 utomaya:第九!!! 數字實在太大了 跑了20分鐘 XD
推 utomaya:如果是2.5*10^10 我只要6秒；數字每增加10倍,時間增加6倍
→ babufong:第九也很強悍了啊XD
推 LPH66:我目前只寫出一個要跑半天的作法orz
→ LPH66:這一陣子要開始作事了所以不太能做題目 QQ
→ LPH66:我的作法用了 Farey sequence 不過看來這不是正解的樣子...
推 utomaya:改進了一下程式 最終結局:91秒, 2.5*10^10只要0.8秒
→ utomaya:數字每增加10倍,時間增加4.8倍左右, 時間複雜度O(n^(2/3))