更新日志
2024/12/08：开工。
欧几里得算法
用途与原理
欧几里得算法，用于求两个数的最大公约数。
其核心原理为：\(\gcd(a,b)=\gcd(b,a\bmod b)\)
证明
首先，我们证明 \(\gcd(a,b)=\gcd(b,a\bmod b)\)。
为了方便证明，这里我们令 \(a>b\)。
\[\because \gcd(a,b)\mid a \text,\gcd(a,b)\mid b\\ \therefore \gcd(a,b)\mid a-\lfloor \frac{a}{b}\rfloor\cdot b\Leftrightarrow \gcd(a,b)\mid a\bmod b\\ \because \gcd(a,b)\mid b,\gcd(a,b)\mid a\bmod b\\ \therefore \gcd(a,b)\mid \gcd(b,a\bmod b) \]
\[\because \gcd(b,a\bmod b)\mid b,\gcd(b,a\bmod b)\mid a\bmod b\\ \therefore\gcd(b,a\bmod b)\mid a\bmod b+\lfloor \frac{a}{b}\rfloor\cdot b\Leftrightarrow \gcd(b,a\bmod b)\mid a\\ \because \gcd(b,a\bmod b)\mid b,\gcd(b,a\bmod b)\mid a\\ \therefore \gcd(b,a\bmod b)\mid \gcd(a,b) \]\[\because \gcd(a,b)\mid \gcd(b,a\bmod b),\gcd(b,a\bmod b)\mid\gcd(a,b)\\ \therefore \gcd(a,b)=\gcd(b,a\bmod b) \]
证毕。
当 \(b\mid a\)时，显然此时 \(\gcd(a,b)=b\)。
证毕。
实现细节
- 实际实现中，我们无需判断 \(a>b\)，类似于
if(a<b)swap(a,b)的操作是不必要的。
假如 \(a<b\)，那么下一步递归时代入的 \(\gcd(b,a\bmod b)=\gcd(b,a)\)，可见没有影响，只多了 \(1\) 的常数。 - 更常见的写法是
if(!b)return a，当然if(a%b==0)return b也没有问题，不过你也可以看出前者更简洁（实际没有多少），只是会多出 \(1\) 的常数，但通常情况下%都是很慢的，所以前者其实并不比后者劣。
模板
int gcd(int a,int b){return (b?gcd(b,a%b):a);}
如果你不喜欢三目运算符或者压行：
int gcd(int a,int b){
if(!b)return a;
return gcd(b,a%b);
}
拓展欧几里得算法
用途
拓展欧几里得算法用来求解形似 \(ax+by=c\) 的线性不定方程。
拓欧常见的利用是求乘法逆元。
原理与证明
首先，我们需要确定上述方程是否有解，根据裴蜀定理，上述方程有解当且仅当 \(\gcd(a,b)\mid c\)。
我们考虑如何借助欧几里得算法求解这个方程。事实上，拓展欧几里得算法是用来求解 \(ax+by=\gcd(a,b)\) 的，但因为 \(\gcd(a,b)\mid c\)，所以我们可以以此为跳板求出原方程的解。
思考 \(ax+by=\gcd(a,b)\) 中 \(x,y\) 与 \(bx'+(a\bmod b)y'=\gcd(b,a\bmod b)\) 中 \(x',y'\) 的关系：
\[\because \gcd(a,b)=\gcd(b,a\bmod b)\\ \therefore ax+by=bx'+(a\bmod b)y'\\ \Leftrightarrow ax+by=bx'+(a-\lfloor\frac{a}{b}\rfloor\cdot b)y'\\ \Leftrightarrow ax+by=ay'+b(x'-\lfloor\frac{a}{b}\rfloor\cdot y')\\ \Rightarrow x=y',y=x'-\lfloor\frac{a}{b}\rfloor\cdot y' \]这样，我们在求 \(\gcd(a,b)\) 的同时，即可求出 \(x,y\)。
考虑边界情况，当 \(b\mid a\) 时，方程式形如：
\[ax+by=b \]显然此时一组可行解为 \(x=0,y=1\)，然后回溯即可。
但并没有结束，我们得到的是 \(ax+by=\gcd(a,b)\) 的解，令之为 \(x',y'\)，不难发现原方程的解为：
\[a\frac{c}{\gcd(a,b)}x'+b\frac{c}{\gcd(a,b)}y'=c\\ \therefore x=\frac{c}{\gcd(a,b)}x',y=\frac{c}{\gcd(a,b)}y' \]实现细节
- 考虑到 \(\gcd\) 我们会在 \(b=0\) 时退出（如果不是这种写法请忽略），此时应使 \(x=1,y=0\)，这样回溯一步就可以使 \(b|a\) 时 \(ax+by=b\) 的解为 \(x=0,y=1\)。
- 上述通过 \(x',y'\) 给 \(x,y\) 赋值的操作有更简洁的写法，可以直接向下传参的时候 \(x'\gets y,y'\gets x\) 且使用引用传参，返回之后 \(y\gets y-\lfloor\frac{a}{b}\rfloor\cdot x\) 即可。
模板
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return d;
}
求乘法逆元
使用 \(\text{exgcd}\) 求乘法逆元的前提是模数与被求的数互质。原因下面会说。
考虑乘法逆元定义：\(ax\equiv 1\pmod p\)，其中 \(x\) 即为 \(a\) 逆元。
我们展开原式可得：
\[ax-\lfloor\frac{a}{p}\rfloor p=1\\ \Leftrightarrow ax+py=1 \]那么就可以用拓欧求解了。根据裴蜀定理，有解的前提是 \(\gcd(a,p)\mid 1\)，等同于 \(a,p\) 互质。
最后的 \(x\) 无需除以 \(\text{gcd}\) 然后再乘 \(1\)，因为这两个都是 \(1\)。
使用格式大概如下：
int x,y;
exgcd(a,p,x,y);
然后 \(x\) 就是 \(a\) 模 \(p\) 意义下的逆元了。
标签：frac,gcd,int,bmod,mid,算法,ax,除法,欧几里得 From： https://www.cnblogs.com/HarlemBlog/p/18593320