[中譯] ProjectEuler 370 Geometric triangles

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 (嗶嗶)時間14年前 (2012/02/05 15:16), 編輯推噓4(404)
留言8則, 3人參與, 最新討論串1/1
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

02/05 20:29, , 1F
第九!!! 數字實在太大了 跑了20分鐘 XD
02/05 20:29, 1F

02/05 20:43, , 2F
如果是2.5*10^10 我只要6秒;數字每增加10倍,時間增加6倍
02/05 20:43, 2F

02/05 20:58, , 3F
第九也很強悍了啊XD
02/05 20:58, 3F

02/05 22:49, , 4F
我目前只寫出一個要跑半天的作法orz
02/05 22:49, 4F

02/05 22:49, , 5F
這一陣子要開始作事了所以不太能做題目 QQ
02/05 22:49, 5F

02/05 22:50, , 6F
我的作法用了 Farey sequence 不過看來這不是正解的樣子...
02/05 22:50, 6F

02/07 19:41, , 7F
改進了一下程式 最終結局:91秒, 2.5*10^10只要0.8秒
02/07 19:41, 7F

02/07 19:42, , 8F
數字每增加10倍,時間增加4.8倍左右, 時間複雜度O(n^(2/3))
02/07 19:42, 8F
文章代碼(AID): #1FBYpFWs (puzzle)
文章代碼(AID): #1FBYpFWs (puzzle)