gcd
gcd 的求法：
暴力求法：
枚举约数。
时间复杂度：$O(\sqrt n)$。
更相减损法：
不断用大的减小的，当 $a,b$ 其中一个为 $0$ 时，另一个就是 $\gcd(a,b)$。
时间复杂度：最坏 $O(n)$。
辗转相除法：
辗转相除法又叫欧几里得算法，是有记载的第一个形式化的算法。
考虑更相减损法慢在哪，例如求 $\gcd(10,2)$ 时，不断$-2$，需要做 $5$ 次。$10-2-2-2….<2$ 是终止的条件。而事实上，减的次数即是：$\lfloor\frac{10}{2}\rfloor$。
所以对于每一次的减，可以简化成除法。即：$\gcd(a,b)=\gcd(a\bmod b,b)$。
同样是用大的模小的即可。
时间复杂度：$O(\log n)$。
Stein 算法：
- $a,b$ 为偶数，$\gcd(a,b)=2\times \gcd(\frac{a}2,\frac{b}{2})$。
- $a$ 为奇数，$b$ 为偶数，则 $\gcd(a,b)=\gcd(a,\frac{b}2)$。
- $a,b$ 为奇数，假设 $a\geq b$，则 $\gcd(a,b)=\gcd(\frac{a-b}{2},b)$。
- $\min\lbrace a,b\rbrace=0$，$\gcd(a,b)=\max\lbrace a,b\rbrace$。
时间复杂度：$O(\log n)$。
gcd 的性质：
质因数分解求 gcd：
$\gcd(a,b)=p_1^{\min(a_1,b_1)}\times…\times p_m^{\min(a_m,b_m)}$。
$\text{lcm}(a,b)=p_1^{\max(a_1,b_1)}\times…\times p_m^{\max(a_m,b_m)}$
gcd 的继承性：
$\gcd(a_1,…,a_n)=\gcd(\gcd(a_1,…,a_{n-1}),a_n)$。
gcd 的势能均摊：
多个数取 $\gcd$，$\gcd$ 单调不增。并且，$\gcd$ 变小会至少 $\times\frac12$，且辗转相除法的时间消耗和 $\gcd$ 的变小次数是息息相关的。
具体而言，求 $\gcd(a_1,…,a_n)$ 的时间复杂度为 $O(n+\log a)$ 而不是 $O(n\log a)$ 的。
因此在具体应用中，例如线段树维护区间 $\gcd$ 时，查询的时间复杂度是 $O(\log n+\log a)$ 的。也正因如此，线段树维护区间 $\gcd$ 和 st 表维护在时间复杂度上没有区别，同时线段树的空间还更具优势。
gcd 的差分性：
根据更相减损法，$\gcd(x,y)=\gcd(x,y-x)$，$\gcd(x,y,z)=\gcd(x,y-x,z-y)$。
容易发现，这是一个差分的形式。
因此，可以利用 gcd 的差分性，维护区间加的区间 $\gcd$ 的问题。
Exgcd：
即扩展欧几里得算法。
若 $a,b$ 是任意两个不全为 $0$ 的整数，则存在整数 $x,y$，使得 $ax+by=\gcd(a,b)$。
采用辗转相除法解 $ax+by=\gcd(a,b)$。
设 $ax_1+by_1=\gcd(a,b)$。
$bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)$
$\because\ \gcd(a,b)=\gcd(b,a\bmod b)$
$\therefore\ $$ax_1+by_1=bx_2+(a\bmod b)y_2$
$\because\ $ $a\bmod b=a-(\lfloor\dfrac{a}{b}\rfloor\times b)$
$\therefore\ $ $ax_1+by_1=bx_2+(a-(\lfloor\dfrac{a}{b}\rfloor\times b))y_2$
$ax_1+by_1=ay_2+bx_2-\lfloor\dfrac{a}{b}\rfloor\times by_2=ay_2+b(x_2-\lfloor\dfrac{a}{b}\rfloor y_2)$
$\therefore\ x_1=y_2,\ y_1=x_2-\lfloor\dfrac{a}{b}\rfloor y_2$
将 $x_2,y_2$ 不断代入递归求解直到 $c_{k+2}=0$，可知边界 $x=1,y=0$。
$c_{k+1}x+c_{k+2}y=\gcd(c_{k+1},c_{k+2})$
$\because\ c_{k+2}=0,\ c_{k+1}=(a,b)$
$\therefore\ x=1,\ y=0$。
注意满足 $ax+by=\gcd(a,b)$ 的 $(x,y)$ 有无限多组，假设 $(x_0,y_0)$ 是其中一组，则所有解为 $(x_0+k\frac{b}{(a,b)},y_0-k\frac{a}{(a,b)}),(k\in\mathbb{Z})$。