中国剩余定理

发布时间 2023-07-31 23:31:50作者: DLSQS

由【物不知数】问题引入:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

意思就是有一个数满足除以3余2,除以5余3,除以7余2。

不过解法还挺公式化的,这里就用变量整理吧

x=a1(mod b1)

x=a2(mod b2)

x=a3(mod b3)

M=b1*b2*b3,c1=M/b1=b2*b3,c2=M/b2=b1*b3,c3=M/b3=b1*b2

求出c1,c2,c3,在他们自己取模的数下的逆元

记他们的逆元分别为d1,d2,d3

所以x=Σai*ci*di(mod M),i从1到3

大概就这样,没啥代码技巧,全靠背啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊我真的会发疯