作者tml (流刑人形)
看板puzzle
标题[中译] ProjectEuler 428 Necklace of circles
时间Tue May 21 06:27:37 2013
428. Necklace of circles
http://projecteuler.net/problem=428
令a, b, c为三正实数。
令W, X, Y, Z为一直线上的四个点，并有|WX| = a，|XY| = b，|YZ| = c，
以及|WZ| = a + b + c。
令C_in为以XY为直径的圆，C_out为以WZ为直径的圆。
如果对三元数组(a, b, c)，存在k≧3个圆序列C_1, C_2, ..., C_k符合下列条件，
则称其为「项链数组」：
‧对所有i≠j，1≦i,j≦k，C_i和C_j的内部均没有交集。
‧对所有1≦i≦k，C_i同时和C_in及C_out相切。
‧对所有1≦i< k，C_i和C_(i+1)相切。
‧C_k和C_1相切。
例如，(5, 5, 5)和(4, 3, 21)均为项链数组，而(2, 2, 5)则不是。
http://projecteuler.net/project/images/p428_necklace.png
令T(n)为项链数组(a, b, c)的组数，其中a, b, c为正整数并且b≦n。
例如T(1) = 9，T(20) = 732以及T(3000) = 438106。
请求出T(1000000000)。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 129.2.129.163
1F：推 jurian0101:这不是算额吗，作得挺像的呢www 05/22 06:40
2F：推 jurian0101:有人有头绪的吗...4,3,21的魔力在哪，任何起始半径都 05/23 22:48
3F：→ jurian0101:满足四个圆两两相切。不知道怎麽回事。 05/23 22:49
4F：推 jurian0101:才24人解开，Hmm...可以慢慢想的样子 05/23 23:04
5F：→ tml:过两个礼拜了...来给个关键字Steiner chain 06/03 17:37