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