线性方程组有无穷多解,求通解,用下列方法解线性方程组,并比较计算结果精读

同余定理

若 ax与b模m的余数相同（其中x为未知数，即所需要求的数），即ax%m=b%m，则这个式子可以记作成ax≡b (mod m)。
设ax对m取模后的余数为r1，则有：ax=y1*m+r1。      ①
同理，设b对m取模后的余数为r2，则有：b=y2*m+r2。      ②
其中y1与y2均为任意整数，此时两者互不相干。
那么我们知道，由于ax%m=b%m，则r1=r2，联立①②得：ax-y1m=b-y2m，移项最后得出方程：

                                                                           ax+my=b

这个方程叫线性同余方程，由于未知数x为一阶的，所以也称为一次同余方程。 这个方程的形式也使它叫作 不定方程。
这个方程的一个性质是：若至少有一组解（x0，y0）能使得这个方程成立，则当且仅当gcd（a，m）|b，即a与m的最大公约数能整除b。（twddy）
如果我们直接求解的话，当然是不行的了~那么接下来会由扩展dlddb算法来求出这个方程的通解。
在接下来之前，我们有牢记一个东西，方程ax+my=b，它是关于（x，y）的一个二元一次方程，切记它的右半边式子是已知的数b。（一般题目推出来，a、b、m都是已知的。求x，y）
设g=gcd（a，m），而扩展dlddb算法只是求方程：ax+my=g的一组特解。

扩展dlddb算法

对于方程：ax+my=g，用ex_gcd（扩欧）求出一组解（x0，y0）满足这个方程。
在gcddlddb算法有得出：a与m的最大公约数就是m与a%m的最大公约数。
其递归写法：

int gcd(int a,int m){if(!m)//若当前除数m1为0，则此时的a1即为所求的gcd（a，m）return a;//返回最大公约数elsereturn gcd(m,a%m);//计算b与a%b的最大公约数，与所求相同}

我们现在考虑，在递归终点，有：m=0，a=g，则此时满足方程ax+my=g，这时的一组解为（1，0）。也就是说，在整个gcd中，一直递归下去，到终点时x1=1，y1=0，是方程的一组解，然而此时的a与m都不等于一开始的初值。 我们要知道，所求的方程ax+my=g中，a与m都是固定的，在a与m已知的情况下，求一组解（x，y），而我们现在依据dlddb算法只求出了，当a=g，m=0时，ax+my=g的解，而不是我们所需要的方程的一组解！

那么我们如何从gcd算法的终点，能不能一层一层地往外，使最后a变成了初值，m也变成了初值，这时的（x，y）即为所求解呢？上面有说，我们已知了最终状态，即逐渐往上推，那么每个状态就相当于已知了下个状态了（因为是从下往上推的）
假设现在是在求a与m的最大公因数，并需要求出x和y使得a * x + m * y= gcd，而我们已知了下个状态：m和a%m的最大公约数g，并已经求出了一组解（x1，y1）使得m*x1+（a % m）*y1= g，下面我们证明一下这两层的关系。
我们知道，a % m=a-（a / m）*m。（这里 / 是整除的意思，比如5 / 2 = 2，5 % 2 = 1 ），那么对于已知的下一个状态，我们可以得到：
g = m * x1+（a-(a / m) * m) * y1
   = m * x1 + a * y1 – (a / m) * m * y1
   = a * y1 + m * (x1 – a / m * y1)
这是我们依据下个状态得到的方程，而这个状态要求的方程为：g = a * x +m * y，对比一下你会发现，当前状态的x 与 y 都与下个已知状态的 x1 y1 有关系：
x = y1
y = x1 – (a / m) * y1

大体上来看，就是说明，每个状态的（x，y）都由之前求gcd时的下一个已知状态的（x1，y1）得来的，故明显是一个从底向上的递归。之前gcd算法，是由上往下递归的终点之后，即为从下往上递归出来，这样我们只需要在递归返回的时候，加入一些变量，来记忆化每个阶段的（x，y），到递归结束回来后，（x0，y0）即为所求方程ax+my=g的一组解。
代码如下：

int ex_gcd(int a,int m,int &x,int &y)//x y这里传的是引用，也可以设置成全局变量，或者局部变量再传指针{if(!m){x=1;//当gcd算法到递归终点时，x应取1y=0;//同样，y应取0，作为递归返回求（x，y）的初值return a;//返回所求的最大公约数g}else{int ans=ex_gcd(m,a%m,x,y);//gcd算法，求解gint temp=x;//设置临时变量temp=x，此时x是下一个解的x，也就是说，此时的x只是上面所提到的x1x=y;//当前状态的x是等于下个解的y1y=temp-(a/m)*y;//求得当前状态的yreturn ans;//使返回值一直都是所求的最大公约数g}}

这样，我们通过扩展dlddb算法，得出了一组解（x0，y0），而这组解仅仅是使得方程：ax + my = g 成立的解而已，它的等式右边并不是我们所需要的b，这点一定要明确。

那么如何通过这特殊的方程，转换成我们所需要的方程呢？

由扩展dlddb算法所求出的特定方程的一组解，推出同余方程的一组解

现在已知一组解（x0，y0），则有：
ax0 + my0 = g
左右两边同时乘以 b / g ，得到：
a * (b / g * x0) + m *(b / g * y0) = b
与同余方程对比：
a * x1 + m * y1 = b
这时候我们会很清楚的发现，同余方程的一组解（x1，y1）可以由（x0，y0）得到：

x1 = (b / g) * x0
y1 = (b / g) * y0

这时候我们终于终于求出了，同余方程的一组解（x1，y1）。
当然，只知道一组解的我们，对同余方程的掌握还不够

由同余方程的一组解推导出这个同余方程的通解

设 i > j ，对于同余方程，有：

联立可以得到：


现在左右两边同时除以g（g = gcd（a，m））得到：

我们知道，若有两个数a和m，他们同时除以最大公约数，之后的商是互质的。所以在上面等式中，如果成立，那么说明，m / g一定是 （xi - xj）的倍数，而 a / g 一定是（yj - yi）的倍数，由于之前假设的是i > j ，所以 -a / g 为（yi - yj）的倍数。
所以我们可以得到，任意两个解x的值之差，一定是m / g的倍数，所以任意一个解X的可以由任意一个解x 通过加减 m /g 的倍数得到, 同理，y如此，则有：

其中k取任意整数，而X，Y 中的k在同余方程上是对应的。
这样我们就得到了同余方程的通解！

通过同余方程通解，算出X的最小正整数解

上面的通解X = (m / g) *k + x可以通过余数的变换得到下面这个式子：

我们这么分析一下：任意的解X都可以由这个式子得出，意思就是说，当X>0时，所有的X通过对 m /g 取余后，都会得出一个介于[0 , m /g ) 的一个解x。
那么会有：

然后看到，所有X>0的解中，存在一个介于0到 m / g 中的解，这个解即为最小正整数解。
进而，你会发现，对于任意一个正整数解X ，让它对 m / g 取余，一定会得到这个最小正整数解x。
要注意的是：若得出的特解 x 为负数，要得到最小正整数解 X ，则需要while(x<0) x+=m/g ，来使得特解先变成一个正整数解，再通过余 m/g 得到 X 。做法也等价于下面所提到的。

注意：
如果取余后的结果为负数，需要加上 m/g 使得变为 x 的最小正整数解。
其次，如果要求的是 y 的最小正整数解，按上面的方程中，理应对 a/g 取模，当然结果为负时，需要加上 a/g 。
还有一点就是，求出的最小正整数解 X 与 Y ，他们不一定满足 aX + mY = b 的，因为他们的 k 值并不一定相同。（意思就是，这个方程有很多解如(x,y) ，只是单独拿出来求出了所有解中，最小正整数的 x 或 y ，而不一定 (X,Y) 是原方程的解）

总结：
通过扩展dlddb算法，解出不定方程：ax + my = g （ g = gcd（a，m）） 的一组解（x0，y0）后，通过对这个不定方程的变换，变成同余方程 ax + my = b ，而这个方程的一组解（x1，y1）由（x0，y0）通过变换而来。再由同余方程的一组解（x1，y1）求得通解（x，y），再由通解得出x的最小正整数解