学术：浅谈欧几里得算法

欧几里得算法

又叫辗转相除法，是求解 的快速算法，时间复杂度为 ，可基于“每次余数至少减半”的原理证明。

这个算法有着美妙的几何理解：在长方形中每次选取宽作正方形并切去，如果一边已被切完而另一边仍有余长，长度就是余数。

扩展欧几里得算法

名为扩展，必有相同。这由来于一个美妙的等式：。没错，正是欧几里得算法。

下面让我们具体看看它的一个应用：解二元一次不定方程。

对于形如

的不定方程，我们可以垫一步，找到

我们能这么干，有两点原因：

1. 根据裴蜀定理，这个不定方程一定有整数解，是一个可行的转化；
2. 我们认为 是这个方程的一个基本情况，展示如下：

对于这个式子，我们可以构造出一个 相同且形式相同的式子，从而实现迭代：

这时，由于

我们就想通过迭代的方式，求解 的子问题，从而用系数 推导出 。发现 运算不是很好描述，所以进行化简：

由于是不定方程，只要我们找到了一组特解，我们就可以通过方程中系数的关系，推导出通解的式子，所以我们就要找到上面方程的一个特解，而这个是显然的，只要对应系数下相等就一定满足：

所以就可以开始递归求解子问题 了，同理，仍然是 的，相当于是在辗转相除的基础上套了一个解不定方程的特解，类似于 中 之间的关系。

代码：

inline pair<LL, LL> exgcd(LL n, LL m) {
    if (m == 0)
        return make_pair(1, 0);
    auto [xx, yy] = exgcd(m, n % m);
    return make_pair(yy, xx - (n / m) * yy);
}

随后基于 求解 的特解，从而推出一般解的形式：

• 由之前推导的， 可以直接判掉无解的情况；
• ，在 同乘 ，得到：
  
• 由此，对应相同系数项相等，可以得到一组特解：
  
• 我们为了得到一般解，就需要在不改变等式关系的情况下加入偏移量 ：
  
• 这个形式并不直接，因为含有 。我们希望得到仅仅和 有关系的式子，这需要把 展开并且通分：
  
• 现在它的形态就是我们想看到的了，我们通过循环，每次同步增加减少绿色部分，调节到合理的区间，比如正整数解，最小正整数解，等等。

注意，以上推导一定要熟悉。当学习的东西越来越多，背诵记忆就是不可能的，我们要理解整个过程，并且能够在极短时间内就正确推导出来，达到正确、可行而且不影响考试时间复杂度的效果。

扩展欧几里得算法的应用

一般的，我们把问题转化为一个不定方程的形式，并且想要得到一个范围内的解，我们可以考虑使用扩展欧几里得算法。

求逆元

注意到 可以写作 ，移项之后可以得到如下形式：

求解的逆元也就是 ，此时就可以使用扩展欧几里得算法了。

两点注意：

1. 逆元仅在 互质的时候存在意义，这个也就是 使用的限制范围了，比费马小定理更加广泛；
2. 该方法求出来的逆元可能是负数（毕竟解方程的时候抛弃了所有的实际意义），所以求出来之后需要加上模数再取模；