求解二元一次方程（难度：2颗星）

亦凉 2022-06-15 10:26 207阅读 0赞

问题描述：

用户输入a,b,c三个整数，求解二元一次方程ax+by=c，如果（x,y）不存在整数解，则输出“No Solution”，否则输出一个整数解（x,y）使得x是最小正整数。

解题思路：

参考我的另外一篇文章“扩展欧几里得算法”

[http://blog.csdn.net/yi\_ming\_he/article/details/72819713][http_blog.csdn.net_yi_ming_he_article_details_72819713]

参考代码：

#include <stdio.h>
    
    typedef __int64 int64;
    
    int64 ExtendGcd(int64 a, int64 b, int64* px, int64* py)
    {
        int64 nRet, temp;
        if (b == 0)
        {
            if (px && py)
            {
                *px = 1;
                *py = 0;
            }
            return a;
        }
    
        nRet = ExtendGcd(b, a % b, px, py);
        if (px && py)
        {
            temp = *px;
            *px = *py;
            *py = temp - a / b * (*py);
        }
        return nRet;
    }
    
    
    
    int main()
    {
        //举例：97x-93y=100
        int64 a, b, c, x, y, nGcd, t;
        scanf_s("%I64d%I64d%I64d", &a, &b, &c);
        nGcd = ExtendGcd(a, b, &x, &y);//此处求得的x,y是方程ax+by=gcd(a,b)的一组解
        if (c % nGcd)//如果余数不为0，则无解
        {
            printf("No Solution");
            return 0;
        }
    
        x = x * (c / nGcd);
        y = y * (c / nGcd);//此处为ax+by=c的一组解
        //printf("x=%d,y=%d\n",x, y);
        //通解公式x=x0+bt,y=y0-at(其中t为任意整数)
        //下面x的最小正整数解
        t = b / nGcd;
        x = (x % t + t) % t < 0 ? (x % t + t) % t + (t > 0 ? t : -t) : (x % t + t) % t;//如果解为负数多加1个公差t就可以了
        y = (c - a * x) / b;
        printf("x=%I64d,y=%I64d\n",x, y);
        return 0;
    }

运行结果：

![这里写图片描述][SouthEast]

[http_blog.csdn.net_yi_ming_he_article_details_72819713]: http://blog.csdn.net/yi_ming_he/article/details/72819713
[SouthEast]: /images/20220615/04ccd639c98d456cb72c3a8aace525f7.png