作者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