C++中国剩余定理的推广算法及其实现+源程序
毕业论文关键词 中国剩余定理；推广；算法；编程实现
一、引言
在古代中国的数学历史上，流传着一个韩信点兵的故事：秦朝末年，楚汉相争.有一次，韩信率领1500名将士和楚国大将李峰交战.经过一场苦战，楚军不敌汉军，节节败退返回营地，而汉军也死伤大约四五百人.于是，韩信也整顿兵马返回大本营.当行至一山坡时，忽然有后军来报，说楚军骑兵追来.汉军本来就已十分疲惫，这时队伍一片哗然.韩信兵马行至坡顶，见敌方人数不足五百骑，便立刻点兵迎敌.他命令士兵3人站成一排，多出2名；接着命令士兵5人站成一排，多出3名；他又命令士兵7人站成一排，又多出2名.韩信马上向将士们宣布：我军有1073名战士，而来敌不足五百，况且我们居高临下，以众击寡，一定可以打败敌人.汉军本来就十分信服自己的统帅，这样一来更是认为韩信是神仙下凡、神机妙算.于是士气大振.交战不久，楚军大败而逃.[1]
看完这个故事我相信大家都会有一个疑问，那就是韩信为什么能仅凭士兵的三次排列就能知道士兵人数呢？其实韩信点兵的求解方法，就是中国剩余定理的一次同余式解法.它是中国古代数学的一项重大创造，并且在世界数学史上具有十分重要的地位.因此下面我就对中国剩余定理进行一些介绍和简单的推广，并进行编程实现.
二、中国剩余定理
1 定理内容
中国剩余定理 设 是两两互素的正整数，那么，对任意整数 ，一次同余方程组
（1）
必有解，且解数为1.事实上，设
, （2）
这里 ， 是满足
（3）
的一个整数（即是 对模 的逆）.那么，同余方程组（1）的解是
. （4）
此外， 与 互素的充分必要条件是 与 互素， .[2]
一次同余式组的解法有许多，主要有歌诀法、不定方程解法、同余解法.例如歌诀法是我国古代数学家对这种同余方程组进行了研究，考虑一般解法，并将解法编成一首歌诀:“三人同行七十稀,五树梅花廿一枝,七子团圆正月半,除百零五便得知.”[4]上面所给出的歌诀法只能解决模为3,5,7的同余式组成的同余式组，这样就会具有很大的局限性，一个歌诀只能解决固定了模不固定余数的解.但是从算法的角度，这种算法却是最优的.歌诀法就是古人具有能解一类题的能力，然后把算法规格化，以便后人使用，这是古代人的智慧的体现.在此另外两种解法就不赘述了.
2 举例及编程实现
在进行编程求解时，希望能设计一个算法使得所编的程序可以解决最一般的问题，这样就不得不抛弃一些问题本身的特性，从中国剩余定理求解本身出发，由上面给出可知同余方程组的一般求解方法.由于问题并不是很复杂，只需编写几个自定义函数即可实现.需要用到的函数有：（1）求最大公约数的算法int GCD(int a,int b)用来判断所给的模是否两两互素.（2）扩展欧几里得算法int64 Extend_Euclid(int64 a, int64 b, int64 &x, int64 &y)用来高效求出最大公约数.（3）中国剩余定理的算法实现int64 China_Reminder(int len, int64 *a, int64 *n)即可实现模互素的一次同余方程组的求解.
上一篇：图像增强的理论研究与应用+源程序