扩展欧几里得

一句话理解

扩展欧几里得求 ax+by=gcd。

为什么要学

能求出一组整数解。

讲解

递归回来时 x,y 翻滚更新。可用来求逆元（当 gcd=1）。

例子

gcd 过程倒推系数。

常见错误

• 有解条件是 gcd 整除右边。
• 解的通项没写。