问题补充说明:过程 原因
中国古代求解一次同余式组(见同余)的方法。是数论中一个重要定来自理。又称中国剩余定理。
注释:360问答三数为abc,余数分别为m1m2m3,%为优图求 今年余计算,&&是“且”运算。孙子定理
1、分别找出能被两个数整除,而满足觉虽层第呼落被第三个整除余一的最小的评止石光测消食本酒表数。
k1%b==k1%c==0&&k1%a==1;
k2%a==k2%c==0&&k2%b==1;
k3%a==k3%b==0&&k3%c==1;
2、将三个未知数乘对应数字的余数再加起来,减去这送几西讲防三个数的最小公倍数的整数倍即得结果。
Answer=晚婷派早则械k1×m1+k2×m2没+k3×m3-P×(a×b标讲识汉目因北×c);
P为满足Answer>0的最践守均额等宪劳带济段感大整数;
或者Answer=(k1×m1+k2×m2+k3×m3)%(a×b×c);
解题思路:
令某数为M,令素数为A,B,C,D,…,Z,已知M/A余a,M/B余b,M/C余c,M/D余d,…,M/Z余z。照半双需带脚吸万抓求M=?
因为A,B,C,D,…,Z为不同的素数叫坐怕映充无火足,故,B*C*D*…花友脸的帝括乱*Z不可能被A整除,有弱天鲁义林参成载等差数列(B*C*D*…*Z)+(B*C*D*…*Z)N中取A个连续项,这A个连续项分别除以A的余数必然存在0,1,2,3,…,A-1,所以,从这A个连续项中能寻找到除以A余1的数。再用除以A余1的这个数加*a其积必然除以A余a,史妒这个除以A余a的数,为能够被素数B*C*D*…*Z整除的数,为第一个数;
再按同样的宁数例拿心种见医门道理,从A*C*D*…*Z的倍数中寻找除以B余b的数异液露,该数具备被素数A,C,D,…,Z整除的特性,为第二个数;
因为,第一个数除以A余a,第二个数能被素数A,C,D,…,Z整除,即能脱斤扬艺配很被A整除,所以,第一个执有对季皇础费知数+第二个数之和,仍然保持除以A余a;
同理,第二个数除以B余b,因第一个数能被B整除,所以,第二个数+第一个数之和,仍然保持除以B余b。即,第一个数+第二个数之和,为满足除以A余a,除以B余b。
依此类推,按上面的方法寻找到除以各素因子的余数的数之总和,为满足除以各素因子余数的条件的数。总和再减去能被这几个素数共同整除的数(A*B*C*D*…*Z)N后,其差仍然保持除以各素因子余数的条件的数。由此构成孙子定理的解法。
(中国剩余定理CRT)设m1,m2,...,mk是两两互素的正整数,即gcd(mi,mj)=1,i≠j,i,j=1,2,...,k
则同余方程组:
x≡b1(modm1)
x≡b2(modm2)
...
x≡bk(modmk)
模[m1,m2,...,mk]有唯一解,即在[m1,m2,...,mk]的意义下,存在唯一的x,满足:
x≡bimod[m1,m2,...,mk],i=1,2,...,k