2013-team4/code/exgcd

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
用扩展欧几里德算法解不定方程ax+by=d.
g=gcd(a, b)，如果d%g==0则方程有解，否则无解.
特解为(x0, y0)，通解为(x, y)=(x0+t*b, y0-t*a)
需要保证a,b都是正整数
返回解满足x>=0且最小
}}}
{{{
LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (b==0) { x=1; y=0; return a; }
    LL g=exgcd(b, a%b, y, x);
    y-=(a/b)*x;
    return g;
}

bool solve(LL a, LL b, LL d)
{
    LL x, y, g;
    g=exgcd(a, b, x, y);
    if (d%g) return false;
    b/=g; a/=g; d/=g;
    x=(x%b*(d%b)%b+b)%b;
    y=(d-a*x)/b;
    return true;
}
}}}

用扩展欧几里德算法解不定方程ax+by=d.
g=gcd(a, b)，如果d%g==0则方程有解，否则无解.
特解为(x0, y0)，通解为(x, y)=(x0+t*b, y0-t*a)
需要保证a,b都是正整数
返回解满足x>=0且最小

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (b==0) { x=1; y=0; return a; }
    LL g=exgcd(b, a%b, y, x);
    y-=(a/b)*x;
    return g;
}
bool solve(LL a, LL b, LL d)
{
    LL x, y, g;
    g=exgcd(a, b, x, y);
    if (d%g) return false;
    b/=g; a/=g; d/=g;
    x=(x%b*(d%b)%b+b)%b;
    y=(d-a*x)/b;
    return true;
}