1、線性求逆元：
for (int i = 2; i < MAXN; i++)inv[i] = mul(inv[mod%i], mod - mod / i, mod);
僅僅兩行代碼，就實現了在$O(n)$的時間內求出1到n對模m的逆元有木有！？
2、求最大公因數：
int gcd(int x, int y){return y ? gcd(y, x%y) : x;}第一次接觸到這樣的代碼時，我的內心是這樣的：
wtf???黑人問號.jpg
3、樹狀數組
對於單點修改區間求和，樹狀數組可謂達到了時空複雜度的極限，甚至不多用額外一字節存儲空間。來看看它的實現：
修改：
void add(int i, int x){for (;i <= n; i += i & -i)tree[i] += x;}查詢：
int sum(int i){int ret = 0;for(; i; i -= i & -i)ret +=tree[i];return ret;}表示記性不好的我看完一遍也記住了呢。
4、zkw線段樹
對於單點修改區間查詢的線段樹，zkw大神實力教你如何1分鐘內碼出代碼：
修改：
void set(int x, int value){val[x += treeLen] = value;while (x >>= 1)pushUp(x);}查詢：
int query(int l,int r){int ret = 0;for (l += treeLen - 1, r += treeLen +1; l ^ r ^ 1; l >>= 1, r >>= 1){if (~l & 1)ret = min(ret, val[l^1]);if (r & 1)ret = min(ret, val[r ^ 1]);}return ret;}以上都是一些十分基礎但真的讓你讚不絕口的算法和數據結構。還有一些稍微複雜一些的栗子，由於手機碼代碼太不方便了，就以後再更吧。（如果有筆誤打錯的地方歡迎指正哈）
5、後綴數組的DC3算法，反正學完它的一瞬間我是明白了，天才和普通人的智商差距簡直比人和狗還大啊。。。
6、快速傅里葉變換的數論版本（即NTT）：學完後有種想去數學系的衝動（還好後來冷靜下來了）。費馬素數群的性質居然和複數完美吻合，不得不說是一種奇蹟啊。
7、主席樹：這是fotile巨佬考場上發明這種數據結構，用於在$O(log n)$的時間複雜度內解決序列區間第k大問題，以及區間內元素的排名。個人感覺他比劃分樹的設計巧妙多了，有一種自然的美感。
8、Pollard因數分解算法：如果你真的把關於時間複雜度的證明一步步看完後，相信你會有一種豁然開朗的感覺。這個算法真正高的地方在於把生日悖論和遞推式循環節巧妙的結合在一起，最後運用遞推方程主定理的理論，使得時間複雜度達到了看似不可能的期望$n^0.25$的數量級。
分享到:
閱讀更多 志語者 的文章
