简单算法实现之《中国剩余定理》
中国剩余定理
这个定理之前没见过，是在RSA算法原理（一）中提到的，想深入了解的可以去读下。
故事背景
- 韩信点兵
秦朝末年，楚汉相争。一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步进逼，楚军乱作一团。交战不久，楚军大败而逃。
题目就是：将军点兵，三三数余2，五五数余3，七七数余2。问兵几何？
- 孙子算经
今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？
答曰：二十三
术曰：三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五，即得。
《孙子算经》里给出了解决办法
步骤一
除3余2 -> 取140
除5余3 -> 取63
除7余2 -> 取30
步骤二：
对上面取到的数求和
140 + 63 + 30 = 233
步骤三
用上面求出的结果减去210，就是结果
233 - 210 = 23
结果也就是23了
不过那140，63，30，还有210是怎么来的呢？这就涉及到中国剩余定理的算法原理了。
中国剩余定理原理
#题目：
设要求的数为x，每个除法的结果分别为k1，k2，k3，那么就有：
[1] x / 3 = k1 + 2
[2] x / 5 = k2 + 3
[3] x / 7 = k3 + 2
1.对步骤一中的式子1求解过程为：取式子2和式子3中除数（5和7）的最小公倍数LCM（35），
然后把这个LCM作为x带入式子1。如果LCM不能适应式子1，就对LCM再加上一个LCM，
然后带入式子1中......直到满足式子1为止。
按照这个求解过程，分别对3个式子求解，取到的结果为：35，63，30
2.把上面求到的结果求和
35 + 63 + 30 = 128
3.这里对3个式子的除数取最小公倍数
3，5，7的最小公倍数为105
然后用上面的结果减去这个最小公倍数，就是结果了
128 - 105 = 23
这里估计有人要问了：这个35也不是140，而且105也不等于210啊？！ 这个不用纠结，这个跟古代数学的发展史有关嘛！ 当然，这是我瞎说的，想要深挖的可以去研究下相关资料。
下面具体说代码实现
首先创建个model类，类里面有除数和余数2个属性，然后提供一个便利构造器，方便使用
@interface CRTModel : NSObject
@property (assign, nonatomic) NSInteger divider;
@property (assign, nonatomic) NSInteger remain;
+(instancetype)modelWithDivider:(NSInteger)divider
remain:(NSInteger)remain;
@end
@implementation CRTModel
+(instancetype)modelWithDivider:(NSInteger)divider remain:(NSInteger)remain
{
CRTModel *model = [[self alloc] init];
model.divider = divider;
model.remain = remain;
return model;
}
@end
还需要用到2个函数，最大公约数GCD和最小公倍数LCM
-(NSInteger)gcdOf:(NSInteger)a and:(NSInteger)b
{
//这里用__block修饰也可以
//这里使用欧几里德算法
static const NSInteger(^GCDRecursionBlock)(NSInteger,NSInteger)
= ^(NSInteger ra, NSInteger rb){
if (!ra || !rb) return MAX(ra, rb);
return GCDRecursionBlock(rb,ra%rb);
};
return GCDRecursionBlock(a,b);
}
//最小公倍数
-(NSInteger)lcmOf:(NSInteger)a and:(NSInteger)b
{
return a * b / [self gcdOf:a and:b]; //最小公倍数等于两数之积除以最大公约数
}
然后开始实现算法
0.先创建3个Model，把题目"抄"一遍
CRTModel *model1 = [CRTModel modelWithDivider:3 remain:2];
CRTModel *model2 = [CRTModel modelWithDivider:5 remain:3];
CRTModel *model3 = [CRTModel modelWithDivider:7 remain:2];
1.取到算法中步骤1的结果：
-(NSInteger)getSubMinNumberOfDivider1:(NSInteger)divider1
divider2:(NSInteger)divider2
andDivider3:(NSInteger)divider3
remainOf3:(NSInteger)remainOf3
{
NSInteger lcm = [self lcmOf:divider1 and:divider2];
NSInteger result = lcm;
while ((result % divider3) != remainOf3) {
result += lcm;
}
return result;
}
NSInteger a = [self getSubMinNumberOfDivider1:model1.divider divider2:model2.divider andDivider3:model3.divider remainOf3:model3.remain];
NSInteger b = [self getSubMinNumberOfDivider1:model2.divider divider2:model3.divider andDivider3:model1.divider remainOf3:model1.remain];
NSInteger c = [self getSubMinNumberOfDivider1:model3.divider divider2:model1.divider andDivider3:model2.divider remainOf3:model2.remain];
2.求和
NSInteger sum = a + b + c;
3.求全部除数的最小公倍数，然后求结果
//使用"更相减损术"
NSInteger lcmOfAll =
[self lcmOf:[self lcmOf:model1.divider and:model2.divider] and:model3.divider];
//求结果
NSInteger result = sum - lcmOfAll;
NSLog(@"计算结果为：%ld + %ld * k (k为自然数)",result,lcmOfAll);
算法代码已经上传GitHub:
https://github.com/Bluelich/MyBlogCode/tree/master/CRTAlgorithm
就这么多了。这是我昨晚回顾RSA加密时候看到的，刚好就学习下了，其实想再复习下欧拉函数什么的，都忘光了！ 有时间就搞！！
