引理：朴素欧几里德||辗转相除法:
扩展欧几里德:
满足裴蜀等式有解(裴蜀等式，不看的话理解为一个等式就可以了)
通解为
为 的特解
接下来是证明
证明:当b=0时,
，所以有解
同理a=0
当a>b>0时
由朴素欧几里德
如果
通解
为 的特解
递归法
typedef long long ll; ll extgcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1; y = 0; return a; } ll ans = extgcd(b, a%b, x, y); ll t = x; x = y; y = t - a / b * y; return ans; }----------------------------------
非递归
推导:
,所以初始条件,
设
当r=0时r2就是gcd(a,b)
int extgcd(int a, int b, int &x, int &y) { int x1 = 1, y1 = 0, r1 = a, x2 = 0, y2 = 1, r2 = b, r, q; while (r2) { q = r1 / r2; r = r1 % r2; r1 = r2; r2 = r; x = x1 - q * x2; x1 = x2; x2 = x; y = y1 - q * y2; y1 = y2; y2 = y; } r = r1; x = x1; y = y1; return r; }
