Pascal同余方程,NOIP2012,Day2在那道同余方程的题中,我在解题报告上看到有“扩展欧几里得算法”这种东西,这里附上原题：可以是代码、伪代码,也可以是解题思路,希望能将“扩展欧几里得算法

Pascal同余方程,NOIP2012,Day2在那道同余方程的题中,我在解题报告上看到有“扩展欧几里得算法”这种东西,这里附上原题：可以是代码、伪代码,也可以是解题思路,希望能将“扩展欧几里得算法
Pascal同余方程,NOIP2012,Day2
在那道同余方程的题中,我在解题报告上看到有“扩展欧几里得算法”这种东西,


这里附上原题：

可以是代码、伪代码,也可以是解题思路,希望能将“扩展欧几里得算法”解释得详细一点,我连“同余”都没有学.

如果有不用高精度乘除法的最好……
不用太快回答,3天之内都行.

Pascal同余方程,NOIP2012,Day2在那道同余方程的题中,我在解题报告上看到有“扩展欧几里得算法”这种东西,这里附上原题：可以是代码、伪代码,也可以是解题思路,希望能将“扩展欧几里得算法
本来就不用高精,你可以去MAXTRIX67博客去看,非常详细地介绍了扩展gcd：
（三）扩展的辗转相除
中国剩余定理是一个很基本的定理.很多数学现象都可以用中国剩余定理来解释.背九九乘法口诀表时,你或许会发现,写下 3 × 1, 3 × 2, ..., 3 × 9 ,它们的个位数正好遍历了 1 到 9 所有的情况. 7 的倍数、 9 的倍数也是如此,但 2 、 4 、 5 、 6 、 8 就不行. 3 、 7 、 9 这三个数究竟有什么特别的地方呢?秘密就在于, 3 、 7 、 9 都是和 10 互质的.比如说 3 ,由于 3 和 10 是互质的,那么根据中国剩余定理,在 0 到 29 之间一定有这样一个数,它除以 3 余 0 ,并且除以 10 余 1 .它将会是 3 的某个整倍数,并且个位为 1 .同样的,在 0 到 29 之间也一定有一个 3 的整倍数,它的个位是 2 ；在 0 到 29 之间也一定有一个 3 的整倍数,它的个位是 3 ……而在 0 到 29 之间,除掉 0 以外, 3 的整倍数正好有 9 个,于是它们的末位就正好既无重复又无遗漏地取遍了 1 到 9 所有的数字.
这表明,如果 a 和 n 互质,那么 a · x mod n = 1 、 a · x mod n = 2 等所有方程都是有解的. 18 世纪的法国数学家 Étienne Bézout 曾经证明了一个基本上与此等价的定理,这里我们姑且把它叫做“ Bézout 定理”.事实上,我们不但知道上述方程是有解的,还能求出所有满足要求的解来.
我们不妨花点时间,把方程 a · x mod n = b 和中国剩余定理的关系再理一下.寻找方程 a · x mod n = b 的解,相当于寻找一个 a 的倍数使得它除以 n 余 b ,或者说是寻找一个数 M 同时满足 M mod a = 0 且 M mod n = b .如果 a 和 n 是互质的,那么根据中国剩余定理,这样的 M 一定存在,并且找到一个这样的 M 之后,在它的基础上加减 a · n 的整倍数,可以得到所有满足要求的 M .因此,为了解出方程 a · x mod n = b 的所有解,我们也只需要解出方程的某个特解就行了.假如我们找到了方程 a · x mod n = b 中 x 的一个解,在这个解的基础上加上或减去 n 的倍数（相当于在整个被除数 a · x 的基础上加上或者减去 a · n 的倍数,这里的 a · x 就是前面所说的 M ）,就能得到所有的解了.
更妙的是,我们其实只需要考虑形如 a · x mod n = 1 的方程.因为,如果能解出这样的方程, a · x mod n = 2 、 a · x mod n = 3 也都自动地获解了.假如 a · x mod n = 1 有一个解 x = 100 ,由于 100 个 a 除以 n 余 1 ,自然 200 个 a 除以 n 就余 2 , 300 个 a 除以 n 就余 3 ,等等,等式右边余数不为 1 的方程也都解开了.
让我们尝试求解 115x mod 367 = 1 .注意,由于 115 和 367 是互质的,因此方程确实有解.我们解方程的基本思路是,不断寻找 115 的某个倍数以及 367 的某个倍数,使得它们之间的差越来越小,直到最终变为 1 .由于 367 除以 115 得 3 ,余 22 ,因而 3 个 115 只比 367 少 22 .于是, 15 个 115 就要比 5 个 367 少 110 ,从而 16 个 115 就会比 5 个 367 多 5 .好了,真正巧妙的就在这里了： 16 个 115 比 5 个 367 多 5 ,但 3 个 115 比 1 个 367 少 22 ,两者结合起来,我们便能找到 115 的某个倍数和 367 的某个倍数,它们只相差 2 ： 16 个 115 比 5 个 367 多 5 ,说明 64 个 115 比 20 个 367 多 20 ,又考虑到 3 个 115 比 1 个 367 少 22 ,于是 67 个 115 只比 21 个 367 少 2 .现在,结合“少 2 ”和“多 5 ”两个式子,我们就能把差距缩小到 1 了： 67 个 115 比 21 个 367 少 2 ,说明 134 个 115 比 42 个 367 少 4 ,而 16 个 115 比 5 个 367 多 5 ,于是 150 个 115 比 47 个 367 多 1 .这样,我们就解出了一个满足 115x mod 367 = 1 的 x ,即 x = 150 .大家会发现,在求解过程,我们相当于对 115 和 367 做了一遍辗转相除：我们不断给出 115 的某个倍数和 367 的某个倍数,通过辗转对比最近的两个结果,让它们的差距从“少 22 ”缩小到“多 5 ”,再到“少 2 ”、“多 1 ”,其中 22, 5, 2, 1 这几个数正是用辗转相除法求 115 和 367 的最大公约数时将会经历的数.因而,算法的步骤数仍然是对数级别的,即使面对上百位上千位的大数,计算机也毫无压力.这种求解方程 a · x mod n = b 的算法就叫做“扩展的辗转相除法”.
注意,整个算法有时也会以“少 1 ”的形式告终.例如,用此方法求解 128x mod 367 = 1 时,最后会得出 43 个 128 比 15 个 367 少 1 .这下怎么办呢?很简单, 43 个 128 比 15 个 367 少 1 ,但是 367 个 128 显然等于 128 个 367 ,对比两个式子可知, 324 个 128 就会比 113 个 367 多 1 了,于是得到 x = 324 .
最后还有一个问题：我们最终总能到达“多 1 ”或者“少 1 ”,这正是因为一开始的两个数是互质的.如果方程 a · x mod n = b 当中 a 和 n 不互质,它们的最大公约数是 d > 1 ,那么在 a 和 n 之间做辗转相除时,算到 d 就直接终止了.自然,扩展的辗转相除也将在到达“多 1 ”或者“少 1 ”之前提前结束.那怎么办呢?我们有一种巧妙的处理方法：以 d 为单位重新去度量 a 和 n （或者说让 a 和 n 都除以 d ）,问题就变成我们熟悉的情况了.让我们来举个例子吧.假如我们要解方程 24 · x mod 42 = 30 ,为了方便后面的解释,我们来给这个方程编造一个背景：说一盒鸡蛋 24 个,那么买多少盒鸡蛋,才能让所有的鸡蛋 42 个 42 个地数最后正好能余 30 个?我们发现 24 和 42 不是互质的,扩展的辗转相除似乎就没有用了.不过没关系.我们找出 24 和 42 的最大公约数,发现它们的最大公约数是 6 .现在,让 24 和 42 都来除以 6 ,分别得到 4 和 7 .由于 6 已经是 24 和 42 的公约数中最大的了,因此把 24 和 42 当中的 6 除掉后,剩下的 4 和 7 就不再有大于 1 的公约数,从而就是互质的了.好了,现在我们把题目改编一下,把每 6 个鸡蛋视为一个新的单位量,比如说“ 1 把”.记住, 1 把鸡蛋就是 6 个鸡蛋.于是,原问题就变成了,每个盒子能装 4 把鸡蛋,那么买多少盒鸡蛋,才能让所有的鸡蛋 7 把 7 把地数,最后正好会余 5 把?于是,方程就变成了 4 · x mod 7 = 5 .由于此时 4 和 7 是互质的了,因而套用扩展的辗转相除法,此方程一定有解.可以解出特解 x = 3 ,在它的基础上加减 7 的整倍数,可以得到其他所有满足要求的 x .这就是改编之后的问题的解.但是,虽说我们对原题做了“改编”,题目内容本身却完全没变,连数值都没变,只不过换了一种说法.改编后的题目里需要买 3 盒鸡蛋,改编前的题目里当然也是要买 3 盒鸡蛋. x = 3 ,以及所有形如 3 + 7n 的数,也都是原方程的解.
大家或许已经看到了,我们成功地找到了 24 · x mod 42 = 30 的解,依赖于一个巧合： 24 和 42 的最大公约数 6 ,正好也是 30 的约数.因此,改用“把”作单位重新叙述问题,正好最后的“余 30 个”变成了“余 5 把”,依旧是一个整数.如果原方程是 24 · x mod 42 = 31 的话,我们就没有那么走运了,问题将变成“买多少盒才能让最后数完余 5 又 1/6 把”.这怎么可能呢?我们是整把整把地买,整把整把地数,当然余数也是整把整把的.因此,方程 24 · x mod 42 = 31 显然无解.
综上所述,如果关于 x 的方程 a · x mod n = b 当中的 a 和 n 不互质,那么求出 a 和 n 的最大公约数 d .如果 b 恰好是 d 的整倍数,那么把方程中的 a 、 n 、 b 全都除以 d ,新的 a 和 n 就互质了,新的 b 也恰好为整数,用扩展的辗转相除求解新方程,得到的解也就是原方程的解.但若 b 不是 d 的整倍数,则方程无解.
扩展的辗转相除法有很多应用,其中一个有趣的应用就是大家小时候肯定见过的“倒水问题”.假如你有一个 3 升的容器和一个 5 升的容器（以及充足的水源）,如何精确地取出 4 升的水来?为了叙述简便,我们不妨把 3 升的容器和 5 升的容器分别记作容器 A 和容器 B .一种解法如下：
1. 将 A 装满,此时 A 中的水为 3 升, B 中的水为 0 升；
2. 将 A 里的水全部倒入 B ,此时 A 中的水为 0 升, B 中的水为 3 升；
3. 将 A 装满,此时 A 中的水为 3 升, B 中的水为 3 升；
4. 将 A 里的水倒入 B 直到把 B 装满,此时 A 中的水为 1 升, B 中的水为 5 升；
5. 将 B 里的水全部倒掉,此时 A 中的水为 1 升, B 中的水为 0 升；
6. 将 A 里剩余的水全部倒入 B ,此时 A 中的水为 0 升, B 中的水为 1 升；
7. 将 A 装满,此时 A 中的水为 3 升, B 中的水为 1 升；
8. 将 A 里的水全部倒入 B ,此时 A 中的水为 0 升, B 中的水为 4 升；
这样,我们就得到 4 升的水了.显然,这类问题可以编出无穷多个来,比如能否用 7 升的水杯和 13 升的水杯量出 5 升的水,能否又用 9 升的水杯和 15 升的水杯量出 10 升的水,等等.这样的问题有什么万能解法吗?有!注意到,前面用 3 升的水杯和 5 升的水杯量出 4 升的水,看似复杂的步骤可以简单地概括为：不断将整杯整杯的 A 往 B 里倒,期间只要 B 被装满就把 B 倒空.由于 3 × 3 mod 5 = 4 ,因而把 3 杯的 A 全部倒进 B 里,并且每装满一个 B 就把水倒掉, B 里面正好会剩下 4 升的水.类似地,用容积分别为 a 和 b 的水杯量出体积为 c 的水,实际上相当于解方程 a · x mod b = c .如果 c 是 a 和 b 的最大公约数,或者能被它们的最大公约数整除,用扩展的辗转相除便能求出 x ,得到对应的量水方案.特别地,如果两个水杯的容积互质,问题将保证有解.如果 c 不能被 a 和 b 的最大公约数整除,方程就没有解了,怎么办?不用着急,因为很显然,此时问题正好也没有解.比方说 9 和 15 都是 3 的倍数,那我们就把每 3 升的水视作一个单位,于是你会发现,在 9 升和 15 升之间加加减减,倒来倒去,得到的量永远只能在 3 的倍数当中转,绝不可能弄出 10 升的水来.这样一来,我们就给出了问题有解无解的判断方法,以及在有解时生成一种合法解的方法,从而完美地解决了倒水问题.
最后,让我们把上一节留下的一点悬念给补完：怎样求解《孙子算经》中的“今有物,不知其数”一题.已知有一堆东西,三个三个数余 2 ,五个五个数余 3 ,七个七个数余 2 ,问这堆东西有多少个?根据中国剩余定理,由于除数 3 、 5 、 7 两两互质,因而在 0 到 104 之间,该问题有唯一的答案.我们求解的基本思路就是,依次找出满足每个条件,但是又不会破坏掉其他条件的数.我们首先要寻找一个数,它既是 5 的倍数,又是 7 的倍数,同时除以 3 正好余 2 .这相当于是在问, 35 的多少倍除以 3 将会余 2 .于是,我们利用扩展的辗转相除法求解方程 35x mod 3 = 2 .这个方程是一定有解的,因为 5 和 3 、 7 和 3 都是互质的,从而 5 × 7 和 3 也是互质的（到了下一节,这一点会变得很显然）.解这个方程可得 x = 1 .于是, 35 就是我们要找到的数.第二步,是寻找这么一个数,它既是 3 的倍数,又是 7 的倍数,同时除以 5 余 3 .这相当于求解方程 21x mod 5 = 3 ,根据和刚才相同的道理,这个方程一定有解.可以解得 x = 3 ,因此我们要找的数就是 63 .最后,我们需要寻找一个数,它能同时被 3 和 5 整除,但被 7 除余 2 .这相当于求解方程 15x mod 7 = 2 ,解得 x = 2 .我们想要找的数就是 30 .现在,如果我们把 35 、 63 和 30 这三个数加在一起会怎么样?它将会同时满足题目当中的三个条件!它满足“三个三个数余 2 ”,因为 35 除以 3 是余 2 的,而后面两个数都是 3 的整倍数,所以加在一起后除以 3 仍然余 2 .类似地,它满足“五个五个数余 3 ”,因为 63 除以 5 余 3 ,另外两个数都是 5 的倍数.类似地,它也满足“七个七个数余 2 ”,因而它就是原问题的一个解.你可以验证一下, 35 + 63 + 30 = 128 ,它确实满足题目的所有要求!为了得出一个 0 到 104 之间的解,我们在 128 的基础上减去一个 105 ,于是正好得到《孙子算经》当中给出的答案, 23 .
已知 M 除以 m 个两两互质的数之后所得的余数,利用类似的方法总能反解出 M 来.至此,我们也就完成了 Mignotte 秘密共享方案的最后一环.
此题只要上裸的扩欧就可以了,只要你看懂了非常简单
http://www.matrix67.com/blog/archives/5100