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