作者babufong (嗶嗶)
看板puzzle
標題[中譯] ProjectEuler 370 Geometric triangles
時間Sun Feb 5 15:16:28 2012
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
1F：推 utomaya:第九!!! 數字實在太大了 跑了20分鐘 XD 02/05 20:29
2F：推 utomaya:如果是2.5*10^10 我只要6秒；數字每增加10倍,時間增加6倍 02/05 20:43
3F：→ babufong:第九也很強悍了啊XD 02/05 20:58
4F：推 LPH66:我目前只寫出一個要跑半天的作法orz 02/05 22:49
5F：→ LPH66:這一陣子要開始作事了所以不太能做題目 QQ 02/05 22:49
6F：→ LPH66:我的作法用了 Farey sequence 不過看來這不是正解的樣子... 02/05 22:50
7F：推 utomaya:改進了一下程式 最終結局:91秒, 2.5*10^10只要0.8秒 02/07 19:41
8F：→ utomaya:數字每增加10倍,時間增加4.8倍左右, 時間複雜度O(n^(2/3)) 02/07 19:42