%%lkx

学习博客

exgcd（扩展欧几里得）

可以用来判断并求解形如\(ax+by=c\)的方程，当且仅当\(gcd(a,b)|c\)时，存在整数解\(x,y\)
也就是说，\(exgcd\)可以用来求解方程\(ax+by=gcd(a,b)\),令\(a=b,b=a\%b\)则有方程\(b*x_1+(a\%b)*y_1=gcd(b,a\% b)\)
又因为\(gcd(a,b)=gcd(b,a\%b)\)，且\(a\%b=a-b*\) \(\lfloor {a/b}\rfloor * y_1=gcd(a,b)\)
整理得：$ay_1+b(x_1-\lfloor {a/b}\rfloor* y_1)=gcd(a,b) $
所以原方程中:\(x=y_1,y=x_1-\lfloor {a/b}\rfloor * y_1\)
所以我们只需递归求\(x_1,y_1\),就能求出\(x,y\)

Code:

void exgcd(int a, int b, int &x, int &y) {
    if(!b) {x = 1, y = 0;return;}
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

谢谢收看， 祝身体健康！