扩展欧几里德

扩展欧几里得 求解不定方程 ax+by=gcd(a, b) 的整数解
对于方程 ax+by=c, 如果 gcd(a, b)|c, 则有解, 解为 ax+by=gcd(a, b) 的解乘以 c/gcd(a, b); 否则无解
long long exgcd(long long a, long long b, long long& x, long long &y)
{
    if (!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    long long t = exgcd(b, a%b, y, x);
    y -= a / b * x;
    return t;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容