【数论】扩展欧几里得

欧几里得算法用于求解最大公因数
主要原理：

int gcd(int a,int b){return b?gcd(b,a%b):a;}

扩展欧几里得算法用于求解二元一次方程

首先了解一下裴蜀定理： <nobr> ax+by=c </nobr>有解当且仅当 <nobr> gcd(a,b)|c </nobr>
那么我们就可以求解 <nobr> ax+by=gcd(a,b) </nobr>

根据这个原理递归求解即可

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

根据这个求得的 <nobr> x，y </nobr>只是一组可行解

如果 <nobr> gcd(a,b)=1 </nobr>,那么如果得到一组解 <nobr> x0,y0 </nobr>，通解就可以表示为 <nobr> x=x0+b×t </nobr>, <nobr> y=y0−a×t </nobr>
如果需要求最小整数解x，我们可以令 <nobr> t=　b　(a　,　b) </nobr>,那么 <nobr> x=(x0%t+t)%t </nobr>即可