這篇講的主要是針對 Shanghai 2009/2010 的 pB - Brute Force Algorithm
對於求 
，我們熟悉的 bigmod 對此當然可以做到 
，
但困難點在於此處的 n 過大，要完整算出來幾乎不可能。一個容易
想到的是，在
的情況下，借助費瑪-歐拉定理，我們可以先
將 n mod φ(b)。
但對 a 和 b 不互質的情況下，我們就要特殊處理了。容易注意到(也
可以證明)，無論 a 與 b 有沒有互質，都有
，
意思是仍然會循環，循環節也是 φ(b) 的倍數，且最遲在 φ(b)
會進入循環。
利用這個，我們直接在 n < φ(b) 的時候使用 bigmod，否則視同進入循
環，直接將 n 換成 φ(b) + [n mod φ(b)]。底下介紹另一種做法。
對於求，設 g = ( a , b ) > 1，則 %5En%5C%3B%5Ctextrm%7Bmod%7D%5C%3B%5Cfrac%7Bb%7D%7Bg%7D)
可以方便的用費
瑪-歐拉定理求得。令其為 r 。依除法原理，有
%5En+%3D+%5Cfrac%7Bb%7D%7Bg%7D%5Ctimes+q+%2B+r)
其中 r 很容易求得。考慮把兩邊同乘上 
，可以得到
所以原問題就轉成了求 
，而且 b 是 g 的倍數。所以現在考慮
我們的新問題：求
且有 z = xy。在此我們選擇遞迴的方法把
原問題轉化成較小的問題，轉化的方式就是改求
，如此一
來可以保證問題的規模適當地縮小(
，否則代表 x = 1，這種情
況答案就是 1。)
一樣，設 g = ( x , y )。若 g = 1，那直接用費瑪-歐拉定理求解。否則列
將兩邊同乘 
得到
一樣，r 可以用費瑪-歐拉定理求得，而原問題轉化為求 
，
且
。這縮小了原問題的規模，遞迴下去即可。最後，再將
上式同乘以 x：
所以這樣就可以求出原問題的解了。
這種做法中，每次用 bigmod 求出 r 的時間複雜度為
，而遞迴
的深度也是 層，因此總時間複雜度就是 
。
想到的是，在
將 n mod φ(b)。
但對 a 和 b 不互質的情況下，我們就要特殊處理了。容易注意到(也
可以證明)，無論 a 與 b 有沒有互質，都有
意思是
會進入循環。
利用這個，我們直接在 n < φ(b) 的時候使用 bigmod，否則視同進入循
環，直接將 n 換成 φ(b) + [n mod φ(b)]。底下介紹另一種做法。
對於求
瑪-歐拉定理求得。令其為 r 。依除法原理，有
我們的新問題：求
原問題轉化成較小的問題，轉化的方式就是改求
來可以保證問題的規模適當地縮小(
況答案就是 1。)
一樣，設 g = ( x , y )。若 g = 1，那直接用費瑪-歐拉定理求解。否則列
且
上式同乘以 x：
這種做法中，每次用 bigmod 求出 r 的時間複雜度為
的深度也是
沒有留言:
張貼留言