【The Balance】拓展欧几里得

今天在学数论中的拓展欧几里得，记录一下例题，加深记忆。

首先引入exgcd的概念，是为了解决形如ax+by=gcd(a,b)的不定方程，求解其最小解和通解

具体的算法证明过程我这里就不再阐述，详情请百度，这里给出俩种计算exgcd的方法

void exgcd(int a,int b,int &g,int &x,int &y)//g为gcd(a,b)
{
    if(!b){g=a,x=1,y=0;}
    else
    {
        exgcd(b,a%b,g,y,x);y-=x*(a/b);
    }
}

int exgcd(int a,int b,int &x,int &y)//返回值为gcd(a,b)
{
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int q=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return q;
}

那么将问题扩大化，假如我们要求解形如ax+by=c的不定方程时呢？
这里给出计算最小解的过程

a/=g,b/=g,d/=g;
int x1=x*d;  x1=(x1%b+b)%b;//以x作为基准 
int y1=(d-a*x1)/b;  y1=abs(y1);//求出一组最小x1+y1

int y2=y*d; y2=(y2%a+a)%a;//以y作为基准
int x2=(d-b*y2)/a; x2=abs(x2);

if(x1+y1<x2+y2) printf("%d %d\n",x1,y1);
else printf("%d %d\n",x2,y2);