Re: [討論] GCJ結束了我要伸解法～
看板Prob_Solve (計算數學 Problem Solving)作者Lucemia (生の直感、死の予感)時間16年前 (2008/07/28 23:41)推噓1(1推 0噓 1→)留言2則, 1人參與討論串2/6 (看更多)
: 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
推
08/03 04:13, , 1F
08/03 04:13, 1F
→
08/03 04:14, , 2F
08/03 04:14, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 6 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
