线性同余方程(组)求解

因为ACM/ICPC中有些题目是关于数论的，特别是解线性同余方程，所以有必要准备下这方面的知识。关于这部分知识，我先后翻看过很多资料，包括 陈景润的《初等数论》、程序设计竞赛例题解、“黑书”和很多网上资料，个人认为讲的最好最透彻的是《算法导论》中的有关章节，看了之后恍然大悟。经过几天 的自学，自己觉得基本掌握了其中的“奥妙”。拿出来写成文章。

那么什么是线性同余方程？对于方程：ax≡b(mod   m)，a，b，m都是整数，求解x 的值。

解题例程：pku1061 青蛙的约会 解题报告

符号说明：

                  mod表示：取模运算

                  ax≡b(mod   m)表示：(ax - b) mod m = 0，即同余

                  gcd(a,b)表示：a和b的最大公约数

求解ax≡b(mod n)的原理：

对于方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整数。而ax≡b(mod n)的解可以由x，y来堆砌。具体做法，见下面的MLES算法。

第一个问题：求解gcd(a,b)

定理一：gcd(a,b) = gcd(b,a mod b)

实现：古老的欧几里德算法

int Euclid(int a,int b)
{
if(b == 0)
      return a;
else
      return Euclid(b,mod(a,b));
}

附：取模运算

int mod(int a,int b)
{
if(a >= 0)
      return a % b;
else
      return a % b + b;
}

第二个问题：求解ax + by = gcd(a,b)

定理二：gcd(b,a mod b) = b * x' + (a mod b) * y'

                                           = b * x' + (a - a / b * b) * y'

                                           = a * y' + b * (x' - a / b *      y')

                                           = a * x + b * y

                  则：x = y'

                         y = x' - a / b * y'

实现：

triple Extended_Euclid(int a,int b)
{
triple result;
if(b == 0)
{
      result.d = a;
      result.x = 1;
      result.y = 0;
}
else
{
      triple ee = Extended_Euclid(b,mod(a,b));
      result.d = ee.d;
      result.x = ee.y;
      result.y = ee.x - (a/b)*ee.y;
}
return result;
}

附：三元组triple的定义

struct triple
{
int d,x,y;
};

第三个问题：求解ax≡b(mod n)

实现：由x，y堆砌方程的解

int MLES(int a,int b,int n)
{
triple ee = Extended_Euclid(a,n);
if(mod(b,ee.d) == 0)
      return mod((ee.x * (b / ee.d)),n / ee.d);
else
      return -1;
}//返回-1为无解，否则返回的是方程的最小解

说明：ax≡b(mod n)解的个数：

           如果ee.d 整除 b 则有ee.d个解；

           如果ee.d 不能整除 b 则无解。

第四个问题：求解a≡bi(mod m[i]),用

中国剩余定理和一次同余方程组的通用解法

今天参加了一家做图形软件的公司的笔试，出了这样一道题：一堆鸡蛋，3个3个数余2，5个5个数余1，7个7个数余6，问这堆鸡蛋最少有多少个？

    作为数学专业出身的我看到这道题当即笑了，因为这是一个很经典的一次同余方程的问题。当然很快就用曾经记得的算法给出了答案101，但我觉得还不过瘾，又因为觉得这类问题对于搞计算机的实在很重要，所以又回忆了一下初等数论的相关理论知识，特此总结一下！

    对于这个问题用数学的语言来描述就是：

        N = 2(mod 3) = 1(mod 5) = 6(mod 7);

    求解最小N。

    由一首诗可以轻易得出求解算法：

   “ 三人同行七十稀，五树梅花甘一枝， 七子团圆正半月，除百零五便得知。”

    即解为：N = 2*70+1*21+6*15-105*n.（n为使得N不为负的最大正整数，这里就是1了）

    那么我们是怎么得到这个公式的呢？

    其实早在几千年前中国的一本《孙子算经》就已经提及这个问题的解法了，原文为：

“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？” 
    答曰：“二十三”
    术曰：“三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五，即得。”

    《孙子算经》的“物不知数”题虽然开创了一次同余式研究的先河，但由于题目比较简单，甚至用试猜的方法也能求得，所以尚没有上升到一套完整 的计算程序和理论的高度。真正从完整的计算程序和理论上解决这个问题的，是南宋时期的数学家秦九韶。秦九韶在他的《数书九章》中提出了一个数学方法“大衍 求一术”（其实就是后来数学王子高斯提出的解同余方程的方法），系统地论述了一次同余式组解法的基本原理和一般程序。

     秦九韶为什么要把他的这一套计算程序和基本原理称为“大衍求一术”呢？这是因为其计算程序的核心问题是要“求一”。所谓“求一”，通俗他 说，就是求“一个数的多少倍除以另一个数，所得的余数为一”。那么为什么要“求一”呢？我们可以从“物不知数”题的几个关键数字70、21、15中找到规 律。

    我们可以看出解此题的关键在于如何确定70、21、15这3个数（105 = 3*5*7）。现简述如下：

    归结为一句话就是求3、5、7三个数两两组合相乘的k倍模另外一个数而余1的数 。这样说可能有点抽象，下面具体讲解下大家就会明白了：

    首先对于5、7两个数，即为：

            70 = 2*5*7  = 1(mod 3)

    其中k为2，所以很容易求出第一个70，同样的道理可以求出：

            21 = 3*7 = 1(mod 5)

            15 = 3*5 = 1(mod 7)

 

    理解了上例解法，我们不难得出著名的中国剩余定理（孙子定理）的一般数学形式了：

    一次同余方程组

             x = a₁(mod m₁)

             x = a₂(mod m₂)

             ...

             x = a_k(mod m_k)

    若m₁,m₂,......,m_k这些数两两互质，且定义m_iM_i = m₁m₂......m_k以及C_iM_i = 1 (mod m_i)。则此一次同余方程组的解为：

        x = a₁M₁C₁ + a₂M₂C₂ + ......+a_kM_kC_k (mod m)。

 

    所以我们可以很容易的把这个面试题推广为：

    一堆鸡蛋，3个3个数余a₁，5个5个数余a₂，7个7个数余a₃，问这堆鸡蛋最少有多少个？

    甚至推广为：

    一堆鸡蛋，n₁个n₁个数余a₁，n₂个n₂个数余a₂，n₃个n₃个数余 a₃ ,....., n_m个n_m个数余a_m，问这堆鸡蛋最少有多少个？（其中n_1,n₂,....., n_m互质）