问题
对于非负整数x,给定n组正整数的除数ai和余数mi(0≤i<n)满足:
xmodai=mi 其中所有余数mi,mj两两互质。设所有余数的乘积为:
M=m0×m1×⋯×mn−1=i=0∏n−1mi 因为任意两个余数互质,显然0≤x<M。
这样的方程组即为数论中的一元线性同余方程组:
(S)=⎩⎨⎧x≡a0(modm0)x≡a1(modm1)⋯x≡an−1(modmn−1) 求x。
数论倒数/模倒数/模逆元
首先介绍数论倒数,三个整数满足:
即:
中国剩余定理
源码
ChineseRemainerTheorem.h
ChineseRemainerTheorem.cpp
测试
ChineseRemainerTheoremTest.cpp