[中譯] ProjectEuler 422 Sequence of points on

[tml (流刑人形)]

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
推 LPH66:這題好樣的...通式算出來了但這 n = 11^14 整個不單純 ._.
→ tml:這題感覺找出通式才是最麻煩的說...
推 LPH66:唔嗯, 我的計算應該只有用到高中數學...
→ LPH66:問題在於我的通式裡有 F_n 在次方上 (眼神死)
→ tml:http://en.wikipedia.org/wiki/Pisano_period 參考看看
推 jurian0101:看gif第一感是這序列搞不好是某種map的偽裝
推 isnoneval:看起來真的很像, 但是把曲線轉正變成 xy = 1 之後
→ isnoneval:就覺得除了次方上的 F_n 之後真的沒有花樣了 XD
→ isnoneval:或許 tml 那條路是正解
→ isnoneval:咦不對, 因為 F_n 在次方上所以應該小費馬就可以了
推 jurian0101:感覺化成最簡分數那步也有點難度吧
推 isnoneval:我沒真的算下去耶, 但應該是座標變換回來那段小心點即可
推 LPH66:最簡分數的部份其實只要算下去就會發現還好  底數只有2跟3
→ LPH66:話說即使用了小費馬還是得求 Pisano(10^9+6) 這很煩...
→ LPH66:因為 10^9+6 分解是 2*(5*10^8+3) 要求後一個大質數的Pisano
→ LPH66:週期實在非常囧...
推 isnoneval:對喔, 忘記 1000000006 超大的 XDDD