解不定方程ax+by=m的最小解

时间：2021-04-11 02:38:50

　　

　　给出方程a*x+b*y=c，其中所有数均是整数，且a，b，c是已知数，求满足那个等式的x，y值？这个方程可能有解也可能没解也可能有无穷多个解（注意：这里说的解都是整数解）？

　　既然如此，那我们就得找出有解和无解的条件！

　　先给出定理：方程a*x+b*y=c有解，当且仅当 c%gcd(a，b)=0。

　　定理的证明很容易，如下：

　　证明：

　　若c%gcd(a，b)=0,则一定存在一个整数K，有c=K*gcd(a，b)， 而我们知道a*x+b*y=gcd(a，b)一定存在解(x1, y1)，所以就有K*(a*x1 +b*y1 )  = K*gcd(a，b)------>a*K*x1 +b*K*y1 = c，得出解为：(K*x1 , K*y1 )。定理得证。

　　那么在a*x+b*y=c有解的情况下如何求解呢？

　　

　　由上可知，a*x+b*y=c 与 a*x+b*y=K*gcd(a,b)是等价的。另外a*x+b*y=gcd(a,b)的一组解为 x1, y1。

　　令a1=a/gcd(a,b), b1=b/gcd(a,b),c1=c/gcd(a,b).

　　综上，我们可以得出x，y的一组解就是x1*c1， y1*c1(实际上这个解我们在上面的证明定理的过程中就可以得出这组解，只是我们要的是最小解，所以在此处给出)，但是满足方程的解有无穷多个，在实际的解题中我们常常只要求其最小解。现以求x的最小解为例，至此我们已经求的一组解使得满足方程a*x+b*y=m，那么a*(x+n*b)+b*(y-n*a)=m显然也成立。可知x+n*b(n=....-2,-1,0,1,2....)就是方程x解集。存在一个k使得x+k*b>0，x的最小解就是(x+k*b)%b.若我们将方程两边同时除以gcd(a,b)，则方程变为a1*x+b1*y=c1，同上分析可知。x的最小值就是（x+k*b1）%b1，由于b1<=b，故这个值定会小于等于之前我们认为最小值。在实际求解时常用while(x<0) x+=b来使得为正的条件满足。

　　另外给出所有解得公式，若x0，y0是该方程的一组整数解，那么该方程的所有整数解可表示为

　　X = x0+b/(a,b)*t;

　　Y = y0-a/(a,b)*t;

代码如下：

　　

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 using namespace std;

 int Exgcd(int a, int b, int &x, int &y)

 {

     if(b==)

     {

         x=, y=;

         return a;

     }

     int r = Exgcd(b, a%b, x, y);

     int tp=x;

     x = y;

     y = tp-a/b*y;

     return r;

 }

 void Liner_qu(int a, int b, int c, int d, int &x, int &y)

 {

     a /= d, b/= d, c /= d;

     x *= c; // 任意一解

     y *= c;

     int tx = x;

     x %= b; //最小解，

     if(x<=) x += (int)abs(b*1.0); //最小整数解

     int k=(tx-x)/b;

     y += k*a; //对应y的最小整数解

     printf("%d %d\n", x, y);

 }

 int main()

 {

     int a, b, c, d, x, y;

     while(~scanf("%d%d%d", &a, &b, &c))

     {

         d = Exgcd(a, b, x, y);

         if(a==&&b==&&c==) puts("1 -1");

         else if((a==&&b==&&c) || c%d || (a&&b==&&c==))

             puts("No solution");

         else if(a&&b==)

             printf("%d %d\n",c/a, -c/a);

         else if(a==&&b)

             printf("1 %d\n",c/b);

         else

             Liner_qu(a, b, c, d, x, y);

     }

     return ;

 }

参考资料：百度百科

　　　　　http://www.cnblogs.com/void/archive/2011/04/18/2020357.html

相关文章