中國(guó)剩余定理
這個(gè)定理之前沒(méi)見(jiàn)過(guò)，是在RSA算法原理（一）中提到的惯豆，想深入了解的可以去讀下。
故事背景
- 韓信點(diǎn)兵
秦朝末年奔害，楚漢相爭(zhēng)楷兽。一次，韓信將1500名將士與楚王大將李鋒交戰(zhàn)华临⌒旧保苦戰(zhàn)一場(chǎng)，楚軍不敵雅潭，敗退回營(yíng)瘪匿，漢軍也死傷四五百人，于是韓信整頓兵馬也返回大本營(yíng)寻馏。當(dāng)行至一山坡，忽有后軍來(lái)報(bào)核偿，說(shuō)有楚軍騎兵追來(lái)诚欠。只見(jiàn)遠(yuǎn)方塵土飛揚(yáng)，殺聲震天漾岳。漢軍本來(lái)已十分疲憊轰绵，這時(shí)隊(duì)伍大嘩。韓信兵馬到坡頂尼荆，見(jiàn)來(lái)敵不足五百騎左腔，便急速點(diǎn)兵迎敵。他命令士兵3人一排捅儒，結(jié)果多出2名液样；接著命令士兵5人一排振亮，結(jié)果多出3名；他又命令士兵7人一排鞭莽，結(jié)果又多出2名坊秸。韓信馬上向?qū)⑹總冃迹何臆娪?073名勇士，敵人不足五百澎怒，我們居高臨下褒搔，以眾擊寡，一定能打敗敵人喷面。漢軍本來(lái)就信服自己的統(tǒng)帥星瘾，這一來(lái)更相信韓信是“神仙下凡”、“神機(jī)妙算”惧辈。于是士氣大振琳状。一時(shí)間旌旗搖動(dòng)，鼓聲喧天咬像，漢軍步步進(jìn)逼算撮，楚軍亂作一團(tuán)。交戰(zhàn)不久县昂，楚軍大敗而逃肮柜。
題目就是：將軍點(diǎn)兵，三三數(shù)余2倒彰，五五數(shù)余3审洞，七七數(shù)余2。問(wèn)兵幾何待讳？
- 孫子算經(jīng)
今有物芒澜，不知其數(shù)，三三數(shù)之创淡，剩二痴晦，五五數(shù)之，剩三琳彩，七七數(shù)之誊酌，剩二，問(wèn)物幾何露乏？
答曰：二十三
術(shù)曰：三三數(shù)之剩二碧浊，置一百四十，五五數(shù)之剩三瘟仿，置六十三箱锐，七七數(shù)之剩二，置三十劳较，并之驹止，得二百三十三浩聋，以二百一十減之，即得幢哨。凡三三數(shù)之剩一赡勘，則置七十，五五數(shù)之剩一捞镰，則置二十一闸与，七七數(shù)之剩一，則置十五岸售，即得践樱。
《孫子算經(jīng)》里給出了解決辦法
步驟一
除3余2 -> 取140
除5余3 -> 取63
除7余2 -> 取30
步驟二：
對(duì)上面取到的數(shù)求和
140 + 63 + 30 = 233
步驟三
用上面求出的結(jié)果減去210，就是結(jié)果
233 - 210 = 23
結(jié)果也就是23了
不過(guò)那140凸丸，63拷邢，30，還有210是怎么來(lái)的呢屎慢？這就涉及到中國(guó)剩余定理的算法原理了瞭稼。
中國(guó)剩余定理原理
#題目：
設(shè)要求的數(shù)為x，每個(gè)除法的結(jié)果分別為k1腻惠，k2环肘，k3，那么就有：
[1] x / 3 = k1 + 2
[2] x / 5 = k2 + 3
[3] x / 7 = k3 + 2
1.對(duì)步驟一中的式子1求解過(guò)程為：取式子2和式子3中除數(shù)（5和7）的最小公倍數(shù)LCM（35）集灌，
然后把這個(gè)LCM作為x帶入式子1悔雹。如果LCM不能適應(yīng)式子1，就對(duì)LCM再加上一個(gè)LCM欣喧，
然后帶入式子1中......直到滿足式子1為止腌零。
按照這個(gè)求解過(guò)程，分別對(duì)3個(gè)式子求解唆阿，取到的結(jié)果為：35益涧，63，30
2.把上面求到的結(jié)果求和
35 + 63 + 30 = 128
3.這里對(duì)3個(gè)式子的除數(shù)取最小公倍數(shù)
3驯鳖，5饰躲，7的最小公倍數(shù)為105
然后用上面的結(jié)果減去這個(gè)最小公倍數(shù)，就是結(jié)果了
128 - 105 = 23
這里估計(jì)有人要問(wèn)了：這個(gè)35也不是140臼隔，而且105也不等于210啊妄壶？摔握！ 這個(gè)不用糾結(jié)，這個(gè)跟古代數(shù)學(xué)的發(fā)展史有關(guān)嘛丁寄！ 當(dāng)然氨淌，這是我瞎說(shuō)的泊愧，想要深挖的可以去研究下相關(guān)資料。
下面具體說(shuō)代碼實(shí)現(xiàn)
首先創(chuàng)建個(gè)model類盛正，類里面有除數(shù)和余數(shù)2個(gè)屬性删咱，然后提供一個(gè)便利構(gòu)造器，方便使用
@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個(gè)函數(shù)豪筝，最大公約數(shù)GCD和最小公倍數(shù)LCM
-(NSInteger)gcdOf:(NSInteger)a and:(NSInteger)b
{
//這里使用歐幾里德算法
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);
}
//最小公倍數(shù)
-(NSInteger)lcmOf:(NSInteger)a and:(NSInteger)b
{
return a * b / [self gcdOf:a and:b]; //最小公倍數(shù)等于兩數(shù)之積除以最大公約數(shù)
}
然后開(kāi)始實(shí)現(xiàn)算法
0.先創(chuàng)建3個(gè)Model痰滋，把題目"抄"一遍
CRTModel *model1 = [CRTModel modelWithDivider:3 remain:2];
CRTModel *model2 = [CRTModel modelWithDivider:5 remain:3];
CRTModel *model3 = [CRTModel modelWithDivider:7 remain:2];
1.取到算法中步驟1的結(jié)果：
-(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.求全部除數(shù)的最小公倍數(shù)，然后求結(jié)果
//使用"更相減損術(shù)"
NSInteger lcmOfAll =
[self lcmOf:[self lcmOf:model1.divider and:model2.divider] and:model3.divider];
//求結(jié)果
NSInteger result = sum - lcmOfAll;
NSLog(@"計(jì)算結(jié)果為：%ld + %ld * k (k為自然數(shù))",result,lcmOfAll);
算法代碼已經(jīng)上傳GitHub:
https://github.com/Bluelich/MyBlogCode/tree/master/CRTAlgorithm
就這么多了续崖。這是我昨晚回顧RSA加密時(shí)候看到的敲街，剛好就學(xué)習(xí)下了，其實(shí)想再?gòu)?fù)習(xí)下歐拉函數(shù)什么的严望，都忘光了多艇！ 有時(shí)間就搞！像吻！
