作者Lucemia (生の直感、死の予感)
看板Prob_Solve
标题Re: [讨论] GCJ结束了我要伸解法～
时间Mon Jul 28 23:41:34 2008
: 1c.Linear Algebra(?)
: 听说是把1当作I,去解 (X-3)^2 = 5 的矩阵X。
: 就可以把(3+sqrt(5))^n 跟那个矩阵做mapping...
: 然後就可以divide and conquer乘次方.
: 但是最後面要怎样转回来不是很理解...
: O(n) (n是数字的encoding长度)
就我知道的部份讲一下
这个解法也是我从其他人听来的线索中拼凑出来的
不确定是否就是最佳解
1. 假设 3 + 5^.5 = X ==> X^2 = 6X -4
由此可以导出递回关析式 X^n = 6X^(n-1) - 4X^(n-2)
但不能直接由此式算出X, X^2後跑回圈去解
因为 X为小数 在乘积的过程会受到原本精准度的影响而产生误差
2. 假设 3 - 5^.5 = Y 假设 An = X^n + Y^n
An 恒为整数 (所有5^..5项会被消掉)
又因为恒 0 < Y^n < 1 因此 X^n 的整数部份为 An - 1
3. 由Y 可以导出 Y^n = 6Y^(n-1) - 4Y^(n-2)
再由A(n) = X^n + Y^n 可导出
A(n) = 6*A(n-1) - 4*A(n-2)
因为 A(n) 皆为整数, 因此可以直接跑回圈累积求解!!
又因为要求的是後三位( %1000的余数), 因此可以直接将
每个A(n) % 1000的值记住就好 A'(n)
到此为止的话 计算时间为 O(n)
之後这部份是有点卡住的地方, 在跑large set 时,
由於n太大如果我将每个A(n)记住, 会产生memory error
跑回圈也嫌太久 很难跑完，因此又再多做了些处理
4*. 由於A'(n) < 1000, An = An-1 + An-2
因此可知 A'n, A'n-1, A'n-2.. 数列 在 1000* 1000内必定循环
求出循环值为 在n = 5 以後, 每100个数列会循环一次
因此 结果等於
if n < 105:
储存好对应的值
else:
n = (n-5) % 100 + 5
计算时间为求得循环点的时间 O(1000000)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.88.50
1F：推 scan33scan33:後来我有听到另一个解法耶！ 08/03 04:13
2F：→ scan33scan33:有机会来分享一下 08/03 04:14