类欧几里得算法

请大家注意：

因为作者写的文章中的梯等式公式总是莫名的显示错误，所以作者的许多文章中的梯等式都暴力拆成一步一个等式了。
造成的不适，请谅解。
同时，如果文章中还有其他错误，请联系作者，谢谢。

学习背景

之前做了一道类欧＋二分的题目，就学一下。

问题模型

求

解法推导

为了方便，我们设
注意，因为取模符号太宽了，所以用C++的"%"来表示取模。

（一）

• 第一种情况：
  这个可以直接推导，比较简单。
  
• 第二种情况：
  这时候我们只要将拆开，就是：
  

（二）

第二类和第一类比较类似，就写得简单一点。

• 第一种情况：
  
• 第二种情况：
  这个也和类似，直接给出结论了：
  

（三）

因为这里涉及到了平方，所以我们考虑用一种求和式表示平方。

之后，有如下推导：

• 第一种情况：
  
  之后，就用与求和类似的方法，得到：
  

• 第二种情况：
  对于这个，就直接将三项式暴力拆开，就有：