作者tml (流刑人形)
看板puzzle
標題[中譯] ProjectEuler 422 Sequence of points on
時間Tue Apr 9 05:52:01 2013
422. Sequence of points on a hyperbola
http://projecteuler.net/problem=422
令H為雙曲線12x^2 + 7xy - 12y^2 = 625。
接著，定義X為H線上的一點(7, 1)。
再來，我們定義一組在H上的點集數列{P_i : i≧1}如下：
‧P_1 = (13, 61/4)。
‧P_2 = (-43/6, -4)。
‧對於所有i>2，P_i為H上異於P_(i-1)的唯一一點使得P_i P_(i-1)平行於P_(i-2) X。
可以證明P_i存在且唯一，並且其坐標值皆為有理數。
http://projecteuler.net/project/images/p422_hyperbola.gif
已知 P_3 = (-19/2 , -229/24)，P_4 = (1267/144, -37/12)以及
P_7 = (17194218091/143327232, 274748766781/1719926784）。
請求出當n = 11^14時P_n的值，答案的格式如下：
若P_n = (a/b, c/d)為分母大於0的最簡分數，那答案即為
(a + b + c + d) mod 1000000007。
例如n = 7時，答案是806236837。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 129.2.129.163
1F：推 LPH66:這題好樣的...通式算出來了但這 n = 11^14 整個不單純 ._. 04/09 10:17
2F：→ tml:這題感覺找出通式才是最麻煩的說... 04/09 11:13
3F：推 LPH66:唔嗯, 我的計算應該只有用到高中數學... 04/09 12:45
4F：→ LPH66:問題在於我的通式裡有 F_n 在次方上 (眼神死) 04/09 12:45
6F：推 jurian0101:看gif第一感是這序列搞不好是某種map的偽裝 04/09 16:25
7F：推 isnoneval:看起來真的很像, 但是把曲線轉正變成 xy = 1 之後 04/10 15:03
8F：→ isnoneval:就覺得除了次方上的 F_n 之後真的沒有花樣了 XD 04/10 15:03
9F：→ isnoneval:或許 tml 那條路是正解 04/10 15:04
10F：→ isnoneval:咦不對, 因為 F_n 在次方上所以應該小費馬就可以了 04/10 15:07
11F：推 jurian0101:感覺化成最簡分數那步也有點難度吧 04/10 19:57
12F：推 isnoneval:我沒真的算下去耶, 但應該是座標變換回來那段小心點即可 04/10 23:03
13F：推 LPH66:最簡分數的部份其實只要算下去就會發現還好 底數只有2跟3 04/10 23:46
14F：→ LPH66:話說即使用了小費馬還是得求 Pisano(10^9+6) 這很煩... 04/10 23:48
15F：→ LPH66:因為 10^9+6 分解是 2*(5*10^8+3) 要求後一個大質數的Pisano 04/10 23:49
16F：→ LPH66:週期實在非常囧... 04/10 23:49
17F：推 isnoneval:對喔, 忘記 1000000006 超大的 XDDD 04/11 13:49