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