数论复习（gcd）

gcd

• gcd有两种求法：gcd(a, b)=gcd(b, a%b)=gcd(a-b, b)

扩展gcd（一种新的写法）

• 找出一对整数((x, y))使得(ax+by=gcd(a,b))

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

• 代码如上，但是这是如何得出的呢？我们来推导一下
• (ax+by=d, bx'+(a mod b)y'=d)
  (bx'+(a-leftlfloorfrac{a}{b} ight floor·b)y'=d)
  (bx'+ay'-leftlfloorfrac{a}{b} ight floor·by'=d)
  (ay'+b(x'-leftlfloorfrac{a}{b} ight floor·y')=d)
  (x=y', y=x'-leftlfloorfrac{a}{b} ight floor·y')
• 然后就变成了求(bx'+(a mod b)y'=d)
• 坚持不懈的递归下去，总能找到b=0的时候，然后就能求x'和y'，再代回去就OK啦！
• 不理解也没问题，老师说代码背会就OK！
• 上面那个好背哦，但是难理解，下面这个就是【真·直译】

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

• OK完美！但是只有这样吗？
• 当然不是。解不一定只有这一种，为了求出更多的解：(ax_1+by_1=ax_2+by_2=d)
  移项(Rightarrow a(x_1-x_2)=b(y_2-y_1))
  除d(Rightarrow a'(x_1-x_2)=b'(y_2-y_1), a'=a/d, b'=b/d)
  显然，a'与b'互质，( herefore x_1-x_2=kb', y_2-y_1=ka')
  ( herefore x_2=x_1-kb', y_2=y_1+ka'(kin Z))

客串一个裴蜀定理

• (ax+by=c)有解，当且仅当(gcd(a, b)|c)
  令(c=gcd(a,b)·k)，两边同除k得(a(x/k)+b(y/k)=gcd(a,b))
  令(x'=x/k, y'=b/k; herefore ax'+by'=gcd(a,b))
  显然我们能求出(x', y')，因此也能求出原来的解。