算法导论——exgcd

exgcd是一种**基于**gcd的算法，为了求得 满足$ax+by=\gcd \left ( a,b \right )$的$x,y$的值（$a,b$已知） 那么，应该怎么实现呢？这是模板，就不多说了： ```cpp int exgcd(int a,int b,int &x,int &y) { if(!b){x=1;y=0;return a;} int d=exgcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y; return d; } ``` 好的，那么它的**时间复杂度**是$O \left ( \log_2 N \right )$，如何证明这里就不说了 那么，最重要的是：它的**应用** 首先，求**逆元**~~别跟我说什么费马小定理~~，先来看下[这题](https://www.luogu.org/problemnew/show/P1082)，这是**求逆元的模板题** 在用exgcd求出**$x,y$的值后，$x \div d$后再** $\% \left ( b \div d \right )$**所求出的值即为$ax \equiv 1 \pmod b$的解（$a$的逆元）** **逆元是什么？它有什么用呢？** 逆元是指在$\pmod m$的环境下，**若$ax \equiv 1$，则称$a$是$x$的逆元**，反之亦然，也可写为$a^{-1} = x \pmod m$，逆元可以将**除法变成乘法**，也就是说，可以**先%再\* **，省去了除法不能%的麻烦 注意：**只有在$ \gcd \left ( a,m\right )=1$的情况下，$ax \equiv 1 \pmod m$才有解** 扩展：**费马小定理是什么呢？** 就是**在$ \gcd \left ( a,p\right )=1$的情况下，$a^{p-1} \equiv 1 \pmod p$**，那么，可以看出若**$p$为质数，则$ \gcd \left ( a,p\right )=1$** 如何**应用它来求逆元**呢？ 只要知道$a^{m-2} \mod m$的结果**就是$a$的逆元**就可以了（注意：**在$m$比较大的情况下，需要使用快速幂**）