这是一个数学推导！！！

 

首先我们已经知道了，如何通过扩展欧几里德算法，求出方程的其中一组解了

那么就可以继续往下看

　　

　　给出两个方程

　　　　ax1+by1=gcd(a,b)

　　　　ax2+by2=gcd(a,b)

　　所以可以推出

　　　　ax1+by1=ax2+by2

　　　　a(x1-x2)=b(y2-y1)

　　然后我们知道gcd(a,b)为a,b的最大公因数，所以我们将 A=a/gcd(a,b)，B=b/gcd(a,b)，接着往下推出

　　　　A(x1-x2)=B(y2-y1)

　　现在A和B两个已经是互素了,所以又可以接着推出

　　　　(这个地方要好好理解，重点！)

　　　　A*(n*B)=B*(m*A)

　　　　(x1-x2)=n*B

　　　　(y2-y1)=m*A

　　这里我们从x入手

　　　　(x1-x2)=n*B

　　　　x1=x2+n*B

　　由此，我们推出了x解的通解公式    x=x0+n*B

　　同理，我们推出了y解的通解公式　y=y0-m*A

 

　　那么我们如果要求 x 的最小整数解,也就是 x0, 不就是这样 x0=x%B

　　但是要记得现在的 x是  ax+by=gcd(a,b)的x

　　我们要求的 X 是  aX+bY=c的X，所以还得先转化  X=x*c/gcd(a,b).

　　然后套入我们的公式

　　X0=X%B

　　X0=X%(b/gcd(a,b))

　　嗯，到此结束，下面给下实现代码

 

　　

void solve() {    int gcd = gcd_pro(a, b, x, y);    if (c % gcd != 0)     {        cout << "无解" << endl;    }    else    {        x = x * c / gcd;        b = b / gcd;        x_min = x % b;        if (x_min <= 0)        {            if (b < 0)b = -b;            x_min += b;        }    }}