最大公约数
更相减损术：\(\gcd(x,y)=\gcd(y-x,x)(x\leq y)\)。
设 \(\gcd(x,y)=k,\gcd(p,q)=1,x=kp,y=kq\)。
那么 \(\gcd(y-x,x)=\gcd(kq-kp,kp)=k\times\gcd(q-p,p)\)。
设 \(\gcd(q-p,p)=r,q-p=rb,p=ra\)。
那么 \(q=r(a+b)\)。
因为 \(\gcd(p,q)=1=\gcd(ra,r(a+b))\)。
所以 \(r=\gcd(a,a+b)=1,\gcd(y-x,x)=k=\gcd(x,y)\)。
辗转相除法（欧几里得算法）：\(\gcd(x,y)=\gcd(y\bmod x,x)(x\leq y)\)。
取模相当于做多次减法，其实就是更相减损术的优化。
最小公倍数
容斥，两数之积除以两数的最大公约数。
有一个小技巧，若数以质因数分解的形式给出，算最大公约数时系数取 \(\min\)，算最小公倍数时系数取 \(\max\)。
拓展欧几里得算法
有不定方程 \(ax+by=\gcd(a,b)\)，求出任意一组整数解（根据裴蜀定理一定有整数解）。
假设我们当前已经得出了方程
\[b\bmod a\times x+ay=\gcd(b\bmod a,a) \]的一组整数解 \(\left\{\begin{array}{lc}x=p\\y=q\end{array}\right.\)，根据 \(\gcd\) 的性质有
\[b\bmod a\times p+aq=\gcd(a,b) \]将取模拆掉
\[\left(b-\left\lfloor\frac{b}{a}\right\rfloor a\right)p+aq=\gcd(a,b) \]整理成最初的形式
\[a\left(q-\left\lfloor\frac{b}{a}\right\rfloor p\right)+bp=\gcd(a,b) \]那么 \(\left\{\begin{array}{lc}x=q-\left\lfloor\frac{b}{a}\right\rfloor p\\y=p\end{array}\right.\) 就是方程 \(ax+by=\gcd(a,b)\) 的一组整数解。
所以在求解 \(ax+by=\gcd(a,b)\) 时我们可以先递归求解 \(b\bmod a\times x+ay=\gcd(b\bmod a,a)\) 然后计算当前的解。
这个递归的终止条件是 \(a=0\)，此时 \(\left\{\begin{array}{lc}x=0\\y=1\end{array}\right.\) 是一组解，返回即可（虽然 \(x\) 取什么都没有关系但我们想让解的绝对值尽量小）。
考虑归纳求出解的范围。假设递归得到 \(\left\{\begin{array}{lc}-b\bmod a\leq y'\leq b\bmod a\\-a\leq x'\leq a\end{array}\right.\)，现在 \(\left\{\begin{array}{lc}x=y'-\left\lfloor\frac{b}{a}\right\rfloor x'\\y=x'\end{array}\right.\)。
取 \(\left\{\begin{array}{lc}y'=b\bmod a\\x'=-a\end{array}\right.\) 有 \(\left\{\begin{array}{lc}x\leq b\bmod a+\left\lfloor\frac{b-b\bmod a}{a}\right\rfloor a\leq b\\y\geq-a\end{array}\right.\)。
取 \(\left\{\begin{array}{lc}y'=-b\bmod a\\x'=a\end{array}\right.\) 有 \(\left\{\begin{array}{lc}x\geq-b\bmod a-\left\lfloor\frac{b-b\bmod a}{a}\right\rfloor a\geq-b\\y\leq a\end{array}\right.\)。
所以拓欧求出的 \(ax+by=\gcd(a,b)\) 的解满足 \(\left\{\begin{array}{lc}x\in[-b,b]\\y\in[-a,a]\end{array}\right.\)，终止边界同样满足。
标签：right,gcd,bmod,欧几里得,lc,算法,array,揭秘,left From： https://www.cnblogs.com/landsol/p/17723506.html