倍增法求LCA
LCA (Least Common Ancestors)，即为最近公共祖先，求LCA也是求树上两点最短路的重要一环。
朴素算法求LCA首先将深度较大的节点沿着父亲向上跳转，与另一点深度相同后同时跳转，直至跳到同一父亲
12345678910111213int lca(int u, int v) { if (depth[u] < depth[v]) { swap(u, v); } while (depth[u] > depth[v]) { u = parent[u]; } while (u != v) { u = parent[u]; v = parent[v]; } return u;}
倍增法求LCA思路大致与朴素算法相同，但跳转时不是一次跳一个父亲，而是跳$2^k$个父亲，跳深度较大的节点时$k$为最大的满足$2^k \leq depth[u]-depth[v]$的数。而共同跳转时，$k$从大 ...
BSGS算法
BSGS算法是一种用于解决离散对数问题的算法，它的全称是Baby Step Giant Step，意为小步大步。然而我并不知到为什么要叫这个名字
离散对数问题假设有一个同余方程$a^x \equiv b \pmod m$，其中$a,b,m$都是给定的整数，$a$与$m$互素。如何求解$x$的值？
第一个想法可能是暴力枚举，将$x$从$0$开始枚举到$m-1$，直到找到一个满足方程的$x$。时间复杂度是$O(m)$，如果$m$很大就挂了。
BSGS算法既然暴力不行，那么我们就要想办法降低时间复杂度。BSGS算法就是一种优化的算法，它的时间复杂度是$O(\sqrt{m})$。它的思想也很简单。
首先我们令$x=A\sqrt{m}-B$，其中$A,B$是两个整数且$0\leq A,B\leq \sqrt{m}$。那么原方程就变成了$a^{A\sqrt{m}-B} \equiv b \pmod m$，即$a^{A\sqrt{m}} \equiv b\cdot a^B \pmod m$。
我们可以将方程分解为两个方程:
\begin{cases}
c \equiv b\cdot a^B \p ...
模意义下的乘法逆元
乘法逆元在我看来就相当于模意义下的除法，在模意义下，如果 $a$ 和 $m$ 互质，那么 $a$ 关于模 $m$ 的乘法逆元 $a^{-1}$ 存在，且满足 $a \times a^{-1} \equiv 1 \pmod m$。
本文主要讲解乘法逆元的四种求法。
费马小定理方法费马小定理表明对于任意整数 $a$ 和素数 $p$，有 $a^{p-1} \equiv 1 \pmod p$。由此我们可以推出 $a \times a^{p-2} \equiv 1 \pmod p$，所以 $a^{p-2}$ 就是 $a$ 关于模 $p$ 的乘法逆元。接下来我们就可以通过快速幂的方法求出 $a^{p-2}$。但要注意的是，这个方法只适用于模数是素数的情况。
123456789LLI qpow(LLI a,LLI b,LLI p){ LLI ans=1; while(b){ if(b&1)ans=ans*a%p; a=a*a%p; b>>=1; } return ans;} ...
扩展欧几里得算法
欧几里得算法是求解两个数的最大公约数的算法，而扩展欧几里得算法则是求解一元线性方程 $ax+by=c$ 的整数解的算法，是欧几里得算法的升级版，也是提高的数论内容中的重要算法之一。
这个算法的原理是利用欧几里得算法求解最大公约数的过程中，不断地更新 $x$ 和 $y$ 的值，直到求解出整数解。具体的过程如下：
设 $a$ 和 $b$ 为两个整数，$d = \gcd(a, b)$，则有 $ax+by=d$。我们可以通过欧几里得算法求出 $d$。
设 $a = b \times k + r$，则有 $d = \gcd(b, r)$，且 $d = bx’+ry’$。将 $r$ 代入，有 $d = bx’+(a-bk)y’$，整理得 $d = ay’+b(x’-ky’)$。因此，我们可以通过递归的方式求解 $x$ 和 $y$。
1234567891011LLI exgcd(LLI a,LLI b,LLI &x,LLI &y){ if(b==0){ x=1,y=0; return a; } LLI d= ...
线段树
线段树真的是一种挺折磨人的数据结构，但它的应用范围也是非常广泛的。它可以在 $O(\log n)$ 的时间内完成区间修改和区间查询。似乎有句话是这么说的：树状数组能做的，线段树都能做；线段树能做的，树状数组不一定能做。
线段树的操作线段树是一种二叉树，它的每一个节点都代表了一个区间。对于一个区间 $[l, r]$，它的左儿子代表了 $[l, mid]$，右儿子代表了 $[mid+1, r]$。其中 $mid = \frac{l+r}{2}$。
依然以区间和为例。
建立通常来说线段树的建立是以递归进行的，由于后面会涉及到区间修改等操作，所以我通常用一个结构体来存储线段树的信息。
1234567891011121314struct{ LLI l,r,sum;}d[4*N];//4倍空间，不然存不下void build(LLI l,LLI r,LLI p){ d[p].l=l,d[p].r=r; if(l==r){//直接存储数值 d[p].sum=a[l]; return; } LLI m=l+((r-l)>>1); bu ...
树状数组
二十天左右的集训结束了，虽然学校的教学完全学不到任何东西，但得承认通过自学学到了不少东西。
自学的第一个知识就是树状数组，它可以在 $O(\log n)$ 的时间内完成单点修改和前缀和查询。由于码量奇少，在搭配上差分数组和权值数组，就能实现许多骚操作。
树状数组的结构以下以维护区间和为例。假设使用$c[i]$数组作为树状数组，它存储了原数组的某一段区间和。右端点是 $i$，左端点是 $i - lowbit(i) + 1$，其中 $lowbit(i)$ 是 $i$ 的二进制表示中最低位的 $1$ 的位置。比方说 $6 = (110)_2$，那么 $lowbit(6) = 2 = (10)_2$。
在树状数组中，每一个 $c[i]$ 都指向父亲 $c[i+lowbit(i)]$。在区间和的情况下，$c[i]$ 存储了 $[i-lowbit(i)+1, i]$ 的区间和。比如 $c[4]$ 存储了 $[1, 4]$ 的区间和。如下图所示：
其中每一层$c[i]$都等于它的子节点之和与原数组以$i$为下标的数值之和，即$c[i] = a[i]+\sum_{j=i-lowbit(i)+1}^{ ...