今天在家裡寫了一整天的大數，好不容易加減乘除都有了，但是乘法的部分FFT還不會寫所以先用做基本的n^2乘法(聽說有一個奇怪的方法叫做Karatsuba演算法也能做大數乘法，還蠻快的)
定義一個大數:
bigN a;//定義大數
以下是大數模板:
2015年1月23日 星期五
2015年1月21日 星期三
[ AVL Tree ] 優化AVL樹
AVL樹是以子樹的高度做為平衡的條件
其平衡條件為:
左子樹的高度與右子樹的高度差不能超過1
因為每次的插入及刪除都有可能壞平衡，所以必須要進行旋轉來修正其平衡性。
共有4種旋轉方法，一序為 : 左左、左右、右右、右左，若想知道關於如何進行平衡的介紹請點擊這裡，其插入刪除常數較大，故其平均效率比Size Balanced Tree要差。
因為在網路上看到很多的AVL樹，其寫法都過於冗長，所以我這邊發一個AVL樹的模板，其code複雜度跟Size Balanced Tree差不多。
主要是將相同的平衡操作合併成一個balanced()函數，插入和刪除完後呼叫即可。
以下為模板:
其平衡條件為:
左子樹的高度與右子樹的高度差不能超過1
因為每次的插入及刪除都有可能壞平衡，所以必須要進行旋轉來修正其平衡性。
共有4種旋轉方法，一序為 : 左左、左右、右右、右左，若想知道關於如何進行平衡的介紹請點擊這裡，其插入刪除常數較大，故其平均效率比Size Balanced Tree要差。
因為在網路上看到很多的AVL樹，其寫法都過於冗長，所以我這邊發一個AVL樹的模板，其code複雜度跟Size Balanced Tree差不多。
主要是將相同的平衡操作合併成一個balanced()函數，插入和刪除完後呼叫即可。
以下為模板:
Treap 模板
這是 旋轉式Treap 的模板，是目前所有平衡樹中code最為簡便的一種。
插入和刪除的時間複雜度跟Randomized binary search tree一樣，是在演算法競賽中最適合使用的平衡樹。
因為 分裂/合併式 Treap 可以完全被 分裂/合併式 Randomized binary search tree取代，故不提供
做法1，完全依靠旋轉進行平衡(刪除速度較慢):
作法2，刪除時合併左右子樹(刪除速度較快):
插入和刪除的時間複雜度跟Randomized binary search tree一樣，是在演算法競賽中最適合使用的平衡樹。
因為 分裂/合併式 Treap 可以完全被 分裂/合併式 Randomized binary search tree取代，故不提供
做法1，完全依靠旋轉進行平衡(刪除速度較慢):
作法2，刪除時合併左右子樹(刪除速度較快):
2015年1月17日 星期六
[ 線性同餘方法 ] 亂數產生器 實做
今天來講幾個簡單的亂數產生方法
主要是利用線性同餘方法來處理的
它的首要條件便是必須符合平均分配率Uniform distribution，也就是在$0 \sim m-1$之間的每個數字, 出現的機率必須相等。
Linear Congruential Method雖是常用法，但也有它的條件:
$X(n+1) = (a \times X(n) + c) \%m$，其中$\%$是取餘數的意思
$X(n+1)$為新的亂數，$X(n)$為前一次產生的亂數。則各參數必須符合下列條件:
如此才能確保產生出來的亂數符合平均分配率，同時也具有最長的重複週期。
以下是在網路上找到的一些不錯的亂數產生方法:
其中random1是Brain大神在處理randomize binary tree的亂數(0xdefaced是質數，defaced是英文單字比較好記)
random2聽說是stdlib裡面的rand()原型，而16807是7的5次方，random2可以產生較rand()大的亂數
random4不是線性同於方法，個人覺得他比較像Subtract with carry的方法
在做[分裂/合併式]randomize binary tree時，其實可以利用seed++的方式當作亂數用(連結中有教學)
主要是利用線性同餘方法來處理的
它的首要條件便是必須符合平均分配率Uniform distribution，也就是在$0 \sim m-1$之間的每個數字, 出現的機率必須相等。
Linear Congruential Method雖是常用法，但也有它的條件:
$X(n+1) = (a \times X(n) + c) \%m$，其中$\%$是取餘數的意思
$X(n+1)$為新的亂數，$X(n)$為前一次產生的亂數。則各參數必須符合下列條件:
- $c$與$m$必須互質。
- 對於任何$m$的質因數$p$，也必須為$a-1$的質因數。
- 若$m$為$4$的倍數，則$a-1$也必須為4的倍數。
如此才能確保產生出來的亂數符合平均分配率，同時也具有最長的重複週期。
以下是在網路上找到的一些不錯的亂數產生方法:
其中random1是Brain大神在處理randomize binary tree的亂數(0xdefaced是質數，defaced是英文單字比較好記)
random2聽說是stdlib裡面的rand()原型，而16807是7的5次方，random2可以產生較rand()大的亂數
random4不是線性同於方法，個人覺得他比較像Subtract with carry的方法
在做[分裂/合併式]randomize binary tree時，其實可以利用seed++的方式當作亂數用(連結中有教學)
c++ rope 基本應用
rope(粗繩)是一個很強大的字串處理物件，聽說是為了與string(細繩)做對比才叫做rope的，其底層是一棵持久化平衡樹，因此在做合併或在中間插入的期望時間是logn
再使用rope前必須在前置作以下的處理
定義一個元素為char的rope:
其實rope本身為了方便已經將rope<char>重新定義為crope
因此也可以這樣寫:
當然rope也可以存取非char的元素
只是有些操作會不支援(例如輸出操作)
對於rope的一些常用操作請參考由SGI網站翻譯的rope成員詳細說明
裡面整理了rope的各種函式及元素
且已經將其翻譯成中文方便閱讀
再使用rope前必須在前置作以下的處理
#include<ext/rope> using namespace __gnu_cxx;
定義一個元素為char的rope:
rope<char> r;
其實rope本身為了方便已經將rope<char>重新定義為crope
因此也可以這樣寫:
crope r;
當然rope也可以存取非char的元素
只是有些操作會不支援(例如輸出操作)
對於rope的一些常用操作請參考由SGI網站翻譯的rope成員詳細說明
裡面整理了rope的各種函式及元素
且已經將其翻譯成中文方便閱讀
Randomized Binary Search Tree 平均深度證明
一棵Randomized Binary Search Tree ，平均深度為2logn
其每個節點成為該顆子樹的根的機率有1/(該顆子樹的大小+1)
對於[分裂/合併式][Split / Merge] Randomized Binary Search Tree 亦同
而其等價於在BST中進行隨機插入
這裡提供嚴謹的證明 連結
以下簡略的證明原自於陳柏叡大大(數奧國手)親筆所寫:
現在總共有n個數，要證說對他隨機排序之後一個一個插入BST得到的平均最大深度=2logn。
那看任意一個數x，他的祖先個數就是它的深度，所以只要算x的祖先個數的期望直。
這只要算，對x以外的每個數y，y當x的祖先的機率是多少，再把他們加起來即可。
但注意到，假設在這n個數(由小到大)排序好的序列裡面，x 排在第 i 個， y 排在第 j 個( y 可以 <x，所以 j 可以 < i )，那麼落在 [ i , j ] ( 或 [ j , i ] )這個區間裡的所有數， y 是第一個被插入BST的(否則會和 y 是 x 的祖先矛盾)，而這件事情發生的機率為 1/( | i - j | +1 ) 。
也就是，如果一個數 y 和 x 在排序好的序列裡面的坐標差 = d 的話，那麼 y 當 x 的祖先的機率就是 1/(d+1)。
所以如果 x 是排序好的序列裡的第 i 個，那所求是
1 / i + 1 / ( i - 1 ) + ... + 1/2 + 1/2 + 1/3 + ... + 1/( n - i + 1 )
<= 2 ( 1/2 + 1/3 + ... + 1/n )
約 = 2logn
其每個節點成為該顆子樹的根的機率有1/(該顆子樹的大小+1)
對於[分裂/合併式][Split / Merge] Randomized Binary Search Tree 亦同
而其等價於在BST中進行隨機插入
這裡提供嚴謹的證明 連結
以下簡略的證明原自於陳柏叡大大(數奧國手)親筆所寫:
現在總共有n個數，要證說對他隨機排序之後一個一個插入BST得到的平均最大深度=2logn。
那看任意一個數x，他的祖先個數就是它的深度，所以只要算x的祖先個數的期望直。
這只要算，對x以外的每個數y，y當x的祖先的機率是多少，再把他們加起來即可。
但注意到，假設在這n個數(由小到大)排序好的序列裡面，x 排在第 i 個， y 排在第 j 個( y 可以 <x，所以 j 可以 < i )，那麼落在 [ i , j ] ( 或 [ j , i ] )這個區間裡的所有數， y 是第一個被插入BST的(否則會和 y 是 x 的祖先矛盾)，而這件事情發生的機率為 1/( | i - j | +1 ) 。
也就是，如果一個數 y 和 x 在排序好的序列裡面的坐標差 = d 的話，那麼 y 當 x 的祖先的機率就是 1/(d+1)。
所以如果 x 是排序好的序列裡的第 i 個，那所求是
1 / i + 1 / ( i - 1 ) + ... + 1/2 + 1/2 + 1/3 + ... + 1/( n - i + 1 )
<= 2 ( 1/2 + 1/3 + ... + 1/n )
約 = 2logn
2015年1月16日 星期五
[smart pointer] [reference counter] 智能指標 引用計數
鑒於有些題目需要記憶體的限制，因此必須要考慮到記憶體的管理。
而智能指標可以幫助我們解決這個問題
在C++11，STL已經有內件shared_ptr，但是速度很慢，而大部分在比賽時會用到的只有引用計數的概念(可以參考Brain大神的blog)，因此我將引用計數(參考自 C++ Template 侯捷譯)部分特別獨立出來，做了一份模板
以下為模板:
用法:
其他的用法可以由下面的代碼看出來(HOJ Problem : 226 - K. CP AC代碼):
其使用了[持久化][分裂/合併式]隨機二分搜尋樹
持久化的部分會在之後介紹
而智能指標可以幫助我們解決這個問題
在C++11，STL已經有內件shared_ptr，但是速度很慢，而大部分在比賽時會用到的只有引用計數的概念(可以參考Brain大神的blog)，因此我將引用計數(參考自 C++ Template 侯捷譯)部分特別獨立出來，做了一份模板
以下為模板:
用法:
reference_pointer<int> a;//建立一個int的引用指標a a = new_reference(5);//a指向新增int動態變數，其值為5 a = new_reference<int>(5);//同上，只是定義較為嚴謹 a = new_reference((int)5);//同上，只是定義較為嚴謹 reference_pointer<int> b = a;//將b指向a所指向之物 struct P{ int a,b; P(int _a,int _b):a(_a),b(_b){} }p(2,3); reference_pointer<P> a;//建立一個P的引用指標a c = new_reference(P(1,2));//指向新增P動態變數，其值為1,2 c = new_reference<P>(P(1,2));//同上，只是定義較為嚴謹 c = new_reference(p);//指向新增P動態變數，其值為p
其他的用法可以由下面的代碼看出來(HOJ Problem : 226 - K. CP AC代碼):
其使用了[持久化][分裂/合併式]隨機二分搜尋樹
持久化的部分會在之後介紹
2015年1月15日 星期四
[分裂/合併式] 隨機二分查找樹 [Split / Merge] Randomized Binary Search Tree
今天來講解可以做區間處理的Randomized Binary Search Tree
好比treap，可以利用拆分跟合併的方式來做區間處理
感謝伯恩大神的指導，請參考其網站
寫起來並不會比需要旋轉的難
先定義他的節點:
可以在裡面增加一些懶惰標記的更新(min,max,rev...等等)
計算節點大小
主要利用[分裂/合併]來進行區間處理
接下來講解分裂(參見 treap分裂):
這是將o按中序將前k個節點分到a，剩下的分到b
合併(參見 treap合併):
這就是隨機的精華所在
每次merge時，a有size(a)/(size(a)+size(b))的機率將a作為root
b反之亦然
而本來random是這樣寫的:
但是看了丁安立魔法師的blog，發現只要x++就好了，也不知道為甚麼
如果只是要做普通的二分搜尋樹，可以利用排名來求出其在整顆樹中的名次，然後再相對應處做插入
插入data可以寫成:
bst.insert(data,bst.rank(data));
刪除也可以用類似的方法處理
旋轉式的randomize bst就可以做這些處理了(其實分裂合併式bst速度有點慢)，那為何還需要 分裂/合併 呢?
我們可以把整顆樹的中序走訪看成是一條陣列
-->因此可以利用它來作區間的維護
像是區間的最大最小值，區間反轉啦，區間移動、刪除等等都可以利用它在logn的時間完成
只須修改其up跟down函數就可以達成目的
凡是線段樹能做到的事情，他都能做到，可以用它來解決很複雜的區間處理問題
注意的是，在有懶惰標記的情況下，如果要詢問一個區間必須在切出那塊區間後先進行down的操作再進行詢問，否則懶惰標記可能沒有被推下去，範例如下:
這個範例up()跟down()也要重寫:
因為應用時分靈活，故不提供樣板，只做介紹
好比treap，可以利用拆分跟合併的方式來做區間處理
感謝伯恩大神的指導，請參考其網站
寫起來並不會比需要旋轉的難
先定義他的節點:
可以在裡面增加一些懶惰標記的更新(min,max,rev...等等)
計算節點大小
主要利用[分裂/合併]來進行區間處理
接下來講解分裂(參見 treap分裂):
這是將o按中序將前k個節點分到a，剩下的分到b
合併(參見 treap合併):
這就是隨機的精華所在
每次merge時，a有size(a)/(size(a)+size(b))的機率將a作為root
b反之亦然
而本來random是這樣寫的:
但是看了丁安立魔法師的blog，發現只要x++就好了，也不知道為甚麼
如果只是要做普通的二分搜尋樹，可以利用排名來求出其在整顆樹中的名次，然後再相對應處做插入
插入data可以寫成:
bst.insert(data,bst.rank(data));
刪除也可以用類似的方法處理
旋轉式的randomize bst就可以做這些處理了(其實分裂合併式bst速度有點慢)，那為何還需要 分裂/合併 呢?
我們可以把整顆樹的中序走訪看成是一條陣列
-->因此可以利用它來作區間的維護
像是區間的最大最小值，區間反轉啦，區間移動、刪除等等都可以利用它在logn的時間完成
只須修改其up跟down函數就可以達成目的
凡是線段樹能做到的事情，他都能做到，可以用它來解決很複雜的區間處理問題
注意的是，在有懶惰標記的情況下，如果要詢問一個區間必須在切出那塊區間後先進行down的操作再進行詢問，否則懶惰標記可能沒有被推下去，範例如下:
這個範例up()跟down()也要重寫:
因為應用時分靈活，故不提供樣板，只做介紹
2015年1月13日 星期二
[ Randomized Binary Search Tree ] 隨機二分查找樹
今天來介紹隨機二分查找樹，因為看了很多外國的文章看了半天都看不懂，現在好不容易看懂英文了，就把它用中文的方式來介紹吧!
隨機二分查找樹，是利用隨機數或機率分布來達到平衡的條件，其證明以附在連結中。
利用隨機數的方法包括Treap，但是這太常見了，所以掠過。
這邊要介紹不需額外再節點紀錄隨機值的方式，透過其節點大小來計算其是否為根或是根據節點大小的比例隨機插入。
維持平衡用左旋根右旋(參見:樹旋轉):
接下來來講解一下它的插入
這裡會用到兩個函數:
insert():插入節點
insert_as_root(node *&p,T k):將k插入子樹p並做為p的根節點
為甚麼要這樣做呢?
當在對節點p進行插入時，新插入點根據隨機分布會有1/(size(p)+1)的機率成為這顆子樹的根
因此可以以遞迴處理
若此節點的值>插入值，則插入其左節點，然後右旋，反之亦然
其常數很小，所以常常插入時間比size balanced tree快，但是深度太大，刪除時間較慢
其平均深度等價於在一棵普通的BST進行隨機插入最終的平均深度，因此為2nlogn
而對於刪除節點，和Treap一樣，有兩種不同的做法:
第一種是透過與左偏樹類似的方法刪除，不需要旋轉，通常效率交高
合併左右子樹，然後刪除其根節點
合併的方式利用了隨機分布的概念
假設需將a,b合併
則有size(a)/(size(a)+size(b))的機率將b合併到a子樹
反之有size(b)/(size(a)+size(b))的機率將a合併到b子樹
第二種作法完全依賴於旋轉
在刪除時如果要被刪除的節點不是一條鏈的話，就按造隨機的概念進行旋轉
有size(左子樹)/(size(左子樹)+size(右子樹))的機率進行右旋
反之有size(右子樹)/(size(左子樹)+size(右子樹))的機率進行左旋
以下為第一種作法(效率較高):
以下為第二種作法:
隨機二分查找樹，是利用隨機數或機率分布來達到平衡的條件，其證明以附在連結中。
利用隨機數的方法包括Treap，但是這太常見了，所以掠過。
這邊要介紹不需額外再節點紀錄隨機值的方式，透過其節點大小來計算其是否為根或是根據節點大小的比例隨機插入。
維持平衡用左旋根右旋(參見:樹旋轉):
接下來來講解一下它的插入
這裡會用到兩個函數:
insert():插入節點
insert_as_root(node *&p,T k):將k插入子樹p並做為p的根節點
為甚麼要這樣做呢?
當在對節點p進行插入時，新插入點根據隨機分布會有1/(size(p)+1)的機率成為這顆子樹的根
因此可以以遞迴處理
若此節點的值>插入值，則插入其左節點，然後右旋，反之亦然
其常數很小，所以常常插入時間比size balanced tree快，但是深度太大，刪除時間較慢
其平均深度等價於在一棵普通的BST進行隨機插入最終的平均深度，因此為2nlogn
而對於刪除節點，和Treap一樣，有兩種不同的做法:
第一種是透過與左偏樹類似的方法刪除，不需要旋轉，通常效率交高
合併左右子樹，然後刪除其根節點
合併的方式利用了隨機分布的概念
假設需將a,b合併
則有size(a)/(size(a)+size(b))的機率將b合併到a子樹
反之有size(b)/(size(a)+size(b))的機率將a合併到b子樹
第二種作法完全依賴於旋轉
在刪除時如果要被刪除的節點不是一條鏈的話，就按造隨機的概念進行旋轉
有size(左子樹)/(size(左子樹)+size(右子樹))的機率進行右旋
反之有size(右子樹)/(size(左子樹)+size(右子樹))的機率進行左旋
以下為第一種作法(效率較高):
以下為第二種作法:
2015年1月10日 星期六
字典樹 Trie
今天完成了字典樹 Trie的模板，可以在O(N) (N=字串長度)的時間搜尋一個字串
插入的時間亦是O(N)，在字串匹配上有很大的幫助(AC字動機)，但是因為每個節點都要記錄所有字元，是非常耗空間的
通常將根節點設為"沒有字元"，若是想進一步了解Trie請自行google吧!
以下為模板:
跟stl map的用法類似
trie<int >t; //定義一個存int的Trie
trie<int ,'a','z'>t //定義一個字元範圍是'a'到'z'的Trie(預設是'A'~'z')
trie<int >::point_iterator it; //定義一個節點迭代器
t.insert("asd",1); //插入1到"asd"的位置(若原來已有值則覆蓋)，傳回插入節點的point_iterator
t.find("asd"); //傳回"asd"位置的point_iterator，若無資料point_iterator為NULL，請注意
t["asf"]; //若"asd"存在資料，傳回其引用位置，若不存在則插入並傳回其引用位置
t.erase("asd"); //刪除"asd"節點，若成功刪除則傳回true，失敗(無結點)則傳回false
t.size(); //傳回字串的總數
t.clear(); //清空trie
插入的時間亦是O(N)，在字串匹配上有很大的幫助(AC字動機)，但是因為每個節點都要記錄所有字元，是非常耗空間的
通常將根節點設為"沒有字元"，若是想進一步了解Trie請自行google吧!
以下為模板:
跟stl map的用法類似
trie<int >t; //定義一個存int的Trie
trie<int ,'a','z'>t //定義一個字元範圍是'a'到'z'的Trie(預設是'A'~'z')
trie<int >::point_iterator it; //定義一個節點迭代器
t.insert("asd",1); //插入1到"asd"的位置(若原來已有值則覆蓋)，傳回插入節點的point_iterator
t.find("asd"); //傳回"asd"位置的point_iterator，若無資料point_iterator為NULL，請注意
t["asf"]; //若"asd"存在資料，傳回其引用位置，若不存在則插入並傳回其引用位置
t.erase("asd"); //刪除"asd"節點，若成功刪除則傳回true，失敗(無結點)則傳回false
t.size(); //傳回字串的總數
t.clear(); //清空trie
2015年1月9日 星期五
2015年1月8日 星期四
2015年1月7日 星期三
在函式中傳入使用者自定函式的方法(C++ Functor 仿函式)
一般來說在函式中傳入使用者自定函式通常會用函數指標
但是C++ template提供了一個較為便利的函數參數，以物件的方式傳入
可支援一般函數或利用重載()運算子所定義的物件
詳情請看代碼:
但是C++ template提供了一個較為便利的函數參數，以物件的方式傳入
可支援一般函數或利用重載()運算子所定義的物件
詳情請看代碼:
2015年1月5日 星期一
歐拉函數 乘法模逆元
今天來講一下歐拉函數及乘法模逆元
首先是歐拉函數
定義: 歐拉函數$φ(N)$是小于或等于$N$的正整數中與$N$互質的數的個數$(N>0)$
其值為
$φ(N)=N \times (1-1/P_1) \times (1-1/P_2) \times (1-1/P_3) \times ... \times (1-1/P_k)$
其中$P_i$為$N$的質因數，總共有$k個$
因此可以利用質數篩法在線性或趨近線性的時間內完成某一區間的歐拉函數:
計算單一數的歐拉函數值可利用平方根質數法求:
接下來介紹乘法模逆元
一整數$A$對同餘$B$之乘法模逆元是指滿足以下公式的整數$R$$$A^{-1}≡R \; (mod \; B)$$
也可以寫成$$AR≡1 \; (mod \; B)$$
根據歐拉定理: 當$gcd(A,B)=1$，$A^{φ(B)} ≡ 1 \; mod \;B$
(若$B$是質數，則$φ(B)=B-1$，競賽題目$B$大多為質數，不需求歐拉函數)
為了方便，我們定義 $X\%Y$ 表示$X$除以$Y$的餘數
顯然 $R=A^{φ(B)-1} \;\% \; B$ 是$A$的模$B$乘法模逆元，可以由次方快速冪再$\ord{logn}$的時間得到:
另一種模逆元的解法:
計算$A$的模$B$乘法模逆元，可由擴展歐幾里得演算法得到
設$exgcd$擴展歐幾里得演算法的函數，它接受兩個整數$A,B$，輸出三個整數$g,x,y$。
$g,x,y$滿足等式$A \times x+B \times y=g$，且$g=gcd(A,B)$。
當$B=0$時，有$x=1,\; y=0$使等式成立
當$B>0$，在歐基里德算法的基礎上，已知$$gcd(A,B)=gcd(B,A\%B)$$
先遞迴求出$x^{'},y^{'}$滿足$$Bx^{'}+(A\%B)y^{'}=gcd(B,A\%B)=gcd(A,B)$$
然後可以將上面的式子化簡得$$Bx^{'}+(A-(A/B) \times B)y^{'}=gcd(A,B)$$$$Ay^{'}+Bx^{'}-(A/B) \times By^{'}=gcd(A,B)$$
這裡的除法是整除法，會自動無條件捨去。把含$B$的因式提取一個$B$，可得$$Ay^{'}+B(x^{'}-(A/B) \times y^{'})=gcd(A,B)$$
故$x=y^{'},\; y=x^{'}-(A/B) \times y^{'}$
若$g=1$，則$A$的模$B$乘法模逆元為$B+x$
$(A \times x+B \times y)\%B=1 \longrightarrow B \times y是B的倍數 \longrightarrow A(x+B)\%B=1 \; (因為x可能小於0)$
總複雜度和歐基里德算法相同，皆為$\ord{logn}$
擴展歐幾里得演算法函數實做:
首先是歐拉函數
定義: 歐拉函數$φ(N)$是小于或等于$N$的正整數中與$N$互質的數的個數$(N>0)$
其值為
$φ(N)=N \times (1-1/P_1) \times (1-1/P_2) \times (1-1/P_3) \times ... \times (1-1/P_k)$
其中$P_i$為$N$的質因數，總共有$k個$
因此可以利用質數篩法在線性或趨近線性的時間內完成某一區間的歐拉函數:
計算單一數的歐拉函數值可利用平方根質數法求:
接下來介紹乘法模逆元
一整數$A$對同餘$B$之乘法模逆元是指滿足以下公式的整數$R$$$A^{-1}≡R \; (mod \; B)$$
也可以寫成$$AR≡1 \; (mod \; B)$$
根據歐拉定理: 當$gcd(A,B)=1$，$A^{φ(B)} ≡ 1 \; mod \;B$
(若$B$是質數，則$φ(B)=B-1$，競賽題目$B$大多為質數，不需求歐拉函數)
為了方便，我們定義 $X\%Y$ 表示$X$除以$Y$的餘數
顯然 $R=A^{φ(B)-1} \;\% \; B$ 是$A$的模$B$乘法模逆元，可以由次方快速冪再$\ord{logn}$的時間得到:
另一種模逆元的解法:
計算$A$的模$B$乘法模逆元，可由擴展歐幾里得演算法得到
設$exgcd$擴展歐幾里得演算法的函數，它接受兩個整數$A,B$，輸出三個整數$g,x,y$。
$g,x,y$滿足等式$A \times x+B \times y=g$，且$g=gcd(A,B)$。
當$B=0$時，有$x=1,\; y=0$使等式成立
當$B>0$，在歐基里德算法的基礎上，已知$$gcd(A,B)=gcd(B,A\%B)$$
先遞迴求出$x^{'},y^{'}$滿足$$Bx^{'}+(A\%B)y^{'}=gcd(B,A\%B)=gcd(A,B)$$
然後可以將上面的式子化簡得$$Bx^{'}+(A-(A/B) \times B)y^{'}=gcd(A,B)$$$$Ay^{'}+Bx^{'}-(A/B) \times By^{'}=gcd(A,B)$$
這裡的除法是整除法，會自動無條件捨去。把含$B$的因式提取一個$B$，可得$$Ay^{'}+B(x^{'}-(A/B) \times y^{'})=gcd(A,B)$$
故$x=y^{'},\; y=x^{'}-(A/B) \times y^{'}$
若$g=1$，則$A$的模$B$乘法模逆元為$B+x$
$(A \times x+B \times y)\%B=1 \longrightarrow B \times y是B的倍數 \longrightarrow A(x+B)\%B=1 \; (因為x可能小於0)$
總複雜度和歐基里德算法相同，皆為$\ord{logn}$
擴展歐幾里得演算法函數實做:
2015年1月1日 星期四
[ size balanced tree ] 節點大小平衡樹 ( 傻B樹 )
訂閱：
文章 (Atom)