算法思想
我们想求得一组\(x,y\)使得 \(ax+by = \gcd(a,b)\)
根据 \(\gcd(a,b) = \gcd(b,a\bmod b)\)
如果我们现在有\(x',y'\) 使得 \(bx'+(a\bmod b)y' = \gcd(b,a\bmod b)\)
那么
$ax+by = bx'+( a-\lfloor\frac a b\rfloor b)y'$
移项之后
\(ax+by = ay'+b(x'-\lfloor\frac a b\rfloor y')\)
我们可以得到一组特解
$x = y',y = x' - \lfloor\frac a b\rfloor y'$
递归求解,当\(b = 0\)时候,\(x = 1,y = 0\);
模板
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x = 1; y = 0;return a;
}
int x1,y1;
int ans = exgcd(b,a%b,x1,y1);
x = y1;
y = x1-(a/b)*y1;
return ans;
}
例题
https://www.luogu.com.cn/problem/P1082