扩展欧几里德算法

从 Trac 迁移的文章

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

原文章内容如下：

 == potaty: ==
{{{
void egcd(ll  a,ll  b,ll  c,ll  &xx,ll  &yy)
{
    if (b==0) 
    {
        xx=c/a;
        yy=0;
        return ;
    }
    ll  x1,x2;
    egcd(b,a%b,c,x1,x2);
    xx=x2;
    yy=x1-(a/b)*x2;
}
}}}

 == erosion: ==
{{{
LL gcd(LL a,LL b)
{
    LL temp;
    //此行错误。不加就是对的。   //if (a<0) a=-a; if (b<0) b=-b;
    while (b!=0) { temp=b; b=a%b; a=temp; }
    return a;
}
//传入的a,b要保证是互质的（因为最后a*1+b*0=1时要保证a为1）
void _gcd(LL a,LL b,LL &x,LL &y)
{
    if (b==0) { x=1,y=0; return; }
    _gcd(b,a%b,x,y);
    LL temp=y;
    y=x-a/b*y; x=temp;
}
}}}

potaty:

void egcd(ll  a,ll  b,ll  c,ll  &xx,ll  &yy)
{
    if (b==0) 
    {
        xx=c/a;
        yy=0;
        return ;
    }
    ll  x1,x2;
    egcd(b,a%b,c,x1,x2);
    xx=x2;
    yy=x1-(a/b)*x2;
}

erosion:

LL gcd(LL a,LL b)
{
    LL temp;
    //此行错误。不加就是对的。   //if (a<0) a=-a; if (b<0) b=-b;
    while (b!=0) { temp=b; b=a%b; a=temp; }
    return a;
}
//传入的a,b要保证是互质的（因为最后a*1+b*0=1时要保证a为1）
void _gcd(LL a,LL b,LL &x,LL &y)
{
    if (b==0) { x=1,y=0; return; }
    _gcd(b,a%b,x,y);
    LL temp=y;
    y=x-a/b*y; x=temp;
}