【模板】扩展欧几里得算法

本文主要是介绍【模板】扩展欧几里得算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

【模板】扩展欧几里得算法

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

如何理解

虽然不知道在推什么但是确实推出来了（？

\[\begin{aligned} \because ax+by&=\gcd(a,b)\\ \gcd(a,b)&=\gcd(b,a \bmod b)\\ \therefore ax+by&=bx+(a \bmod b)y\\ &=bx+(a-\left\lfloor\dfrac{a}{b}\right\rfloor b)y\\ \therefore ax+by&=ay+b(x-\left\lfloor\dfrac{a}{b}\right\rfloor y) \end{aligned} \]

代码的第4~7行就是从从最后得到的 \(ax+by=ay+b(x-\left\lfloor\dfrac{a}{b}\right\rfloor y)\) 得到的。

这篇关于【模板】扩展欧几里得算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！