Project Euler Problem 276, 268, 347

〇〇 · 发表于 2012-2-7 07:37

〇〇发表于 2012-2-6 14:29
从前几个结果看出：要么a c都是完全平方数，要么都是完全平方数的同样的倍数

A SQRT(A*C) ...

感觉也可以筛法
a先从质数平方a0^2开始试验，如果不成功，再试验x*a0^2 成功一个，然后后面n个都可筛掉

tree_new_bee · 发表于 2012-2-8 23:13

〇〇发表于 2012-2-6 14:29
从前几个结果看出：要么a c都是完全平方数，要么都是完全平方数的同样的倍数

A SQRT(A*C) ...

与做Q75时同样，可以把Geometric triangles 分成素的和非素的。
素Geometric triangles 就是说gcd(a,b,c)=1
100以内满足这样条件的：

      A  SQRT(A*C)       C
---------- ---------- ----------
      4       6       9
      9       12       16
      16       20       25
      25       30       36
      25       35       49
      25       40       64
      36       42       49
      49       56       64
      49       63       81
      49       70       100
      64       72       81
      81       90       100

可以看到a/c都是完全平方数。
证明方法暂时没想到。

lastwinner · 发表于 2012-2-8 23:27

本帖最后由 lastwinner 于 2012-2-8 23:27 编辑

〇〇发表于 2012-2-6 12:33
Problem 370
05 February 2012

周长不超过10^6的三角形，如果三边长a/b/c满足a/b/c均为整数，a<=b<=c且b^2 = a * c，那么这样的三角形共有861805 个
请问，若周长不超过2.5·10^13，这样的三角形共有多少个？
不知我翻译的对不对？

tree_new_bee · 发表于 2012-2-8 23:34

本帖最后由 tree_new_bee 于 2012-2-8 23:59 编辑

把上面的数，给出出a/b=b/c的最简化分数：
A       SQRT(A*C)       C
4       6       9       2/3
9       12       16       3/4
16       20       25       4/5
25       30       36       5/6
25       35       49       5/7
25       40       64       5/8
36       42       49       6/7
49       56       64       7/8
49       63       81       7/9
49       70       100       7/10
64       72       81       8/9
81       90       100       9/10

就可以看到构造方法了：取数对p,q, 使得gcd(p,q)=1, 且p<q<2p (证明: 因为p+q >q*q/p 且q>p, 所以pp+pq>qq, 所以2pq>qq, 所以2p>q)
然后，用p^2, p*q, q^2, 就可以构造出素Geometric triangles。

tree_new_bee · 发表于 2012-2-8 23:53

本帖最后由 tree_new_bee 于 2012-2-9 00:32 编辑

采用上面的算法，计算与OO相同的参数(每边不超过10000，周长小于1e6), 时间只要2秒左右了。

with targ as (select 1e4 arg from dual)
, tp as(select level p from targ connect by level <=sqrt(arg))
,tq as(select level q from targ connect by level <=sqrt(arg))
, tabc as (select p*p a, p*q b, q*q c from tp, tq
where p<q and p+q > q*q/p
and pkg_prim2.gcd(p,q) = 1
)
,tmul as (select a*m a, b*m b, c*m c  from tabc, targ, (select level m from targ connect by level<=arg/4)
where (a+b+c)*m < 1e6
and a*m <= arg and b*m <= arg and c*m<=arg
)
select count(*) from tmul

  COUNT(*)
----------
   8341

Executed in 1.997 seconds

(代码只是为了保持与OO一致，实际上有问题， p<q,遗漏了p=q的情况)
但应付题目中的参数，还远远不够。
与Q75一样，性能问题不在于构造素Geometric triangles，而在于后面的循环(tmul部分)。
SQL中无法对那个循环的界限细调，还是要改用pl/sql来写，明天继续。

lastwinner · 发表于 2012-2-9 00:10

本帖最后由 lastwinner 于 2012-2-9 00:10 编辑

tree_new_bee 发表于 2012-2-8 23:34
把上面的数，给出出a/b=b/c的最简化分数：
A SQRT(A*C) C
4 6 9 ...

a/b挺有规律的
不过既然4 6 9满足题设
那么40 60 90也满足题设，不知你有否漏算？
TNB好久不见，不知过年可好？

tree_new_bee · 发表于 2012-2-9 00:13

tree_new_bee 发表于 2012-2-8 23:34
把上面的数，给出出a/b=b/c的最简化分数：
A SQRT(A*C) C
4 6 9 ...

就可以看到构造方法了：取数对p,q, 使得gcd(p,q)=1, 且p<q<2p (证明: 因为p+q >q*q/p 且q>p, 所以pp+pq>qq, 所以2pq>qq, 所以2p>q)
然后，用p^2, p*q, q^2, 就可以构造出素Geometric triangles。

复制代码

证明：
因为 p^2 * q^2 = (p*q)^2, 所以构造的数一定是Geometric triangles
下面证明完备性：
设a,b,c是满足条件的素Geometric triangles，即 a/b = b/c, 且gcd(a,b,c)=1
则假设a/b, b/c可化简为p/q, p和q互质
因为a/b = p/q, 所以存在m 使得a =mp b=mq
因为b/c = p/q, 所以存在n 使得b =np c=nq
所以 mq = np, 即m/n = p/q
因为p/q互质，且a,b,c互质，所以m,n互质
（如果m,n不互质，则假设m=kp, n=kq,(k>1), 则a=kpp, b=kpq, c= kqq, a,b,c有共同的因子k, 与 a,b,c互质矛盾)
因此 m=p, n=q

所以a=mp=p*p, b=mq = p*q, c= nq=q*q

也即素Geometric triangles一定能以p^2,p*q, q*q的方式来表示。

顺带证明了92#的结论：