震撼消息！人类文明原来是因为这八段代码才进入的新时代

分享几个第一次看到就被它的优美深深震撼到的代码：

1、线性求逆元：

for(int i =2; i < MAXN; i++)inv[i] = mul(inv[mod%i],mod-mod/ i,mod);

仅仅两行代码，就实现了在$O(n)$的时间内求出1到n对模m的逆元有木有！？

2、求最大公因数：

intgcd(intx,inty){returny ? gcd(y, x%y) : x;}

第一次接触到这样的代码时，我的内心是这样的：

wtf???黑人问号.jpg

3、树状数组

对于单点修改区间求和，树状数组可谓达到了时空复杂度的极限，甚至不多用额外一字节存储空间。来看看它的实现：

修改：

voidadd(inti,intx){for(;i <= n; i += i & -i)tree[i] += x;}

查询：

intsum(inti){intret =0;for(; i; i -= i & -i)ret +=tree[i];returnret;}

表示记性不好的我看完一遍也记住了呢。

4、zkw线段树

对于单点修改区间查询的线段树，zkw大神实力教你如何1分钟内码出代码：

修改：

voidset(intx,intvalue){val[x += treeLen] =value;while(x >>=1)pushUp(x);}

查询：

intquery(int l,int r){intret =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]);}returnret;}

以上都是一些十分基础但真的让你赞不绝口的算法和数据结构。还有一些稍微复杂一些的栗子，由于手机码代码太不方便了，就以后再更吧。（如果有笔误打错的地方欢迎指正哈）

5、后缀数组的DC3算法，反正学完它的一瞬间我是明白了，天才和普通人的智商差距简直比人和狗还大啊。。。

6、快速傅里叶变换的数论版本（即NTT）：学完后有种想去数学系的冲动（还好后来冷静下来了）。费马素数群的性质居然和复数完美吻合，不得不说是一种奇迹啊。

7、主席树：这是fotile巨佬考场上发明这种数据结构，用于在$O(log n)$的时间复杂度内解决序列区间第k大问题，以及区间内元素的排名。个人感觉他比划分树的设计巧妙多了，有一种自然的美感。

8、Pollard因数分解算法：如果你真的把关于时间复杂度的证明一步步看完后，相信你会有一种豁然开朗的感觉。这个算法真正高的地方在于把生日悖论和递推式循环节巧妙的结合在一起，最后运用递推方程主定理的理论，使得时间复杂度达到了看似不可能的期望$n^0.25$的数量级。

其实现在感觉一切和数据结构或数学有关的算法都是非常优美的，前者在于设计的精巧性，后者在于证明的环环相扣，达到引人入胜的效果。