ChineseRemainerTheorem 中国剩余定理
问题
对于非负整数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。
数论倒数/模倒数/模逆元
首先介绍数论倒数,三个整数满足:
a×bmodm=1 即:
a×b≡1(modm) 则称b是a关于m的数论倒数,也称模倒数、模逆元。显然gcd(a,m)即为a关于m的模逆元,可以通过Euclid求出。
中国剩余定理
用中国剩余定理求解一元线性同余方程组。设除了mi之外所有余数的乘积为:
Mi=miM 因为所有余数两两互质,因此存在ti为Mi关于mi的模逆元,即:
ti×Mi≡1(modmi) 可得方程组(S)的通解形式为:
x=a0⋅t0⋅M0+a1⋅+t1⋅M1+⋯+an−1⋅tn−1⋅Mn−1+k×M=k×M+i=0∑n−1ai⋅ti⋅Mi 其中k为整数,0≤i<n。
对于M取模,则有唯一解:
x=i=0∑n−1ai⋅ti⋅Mi 该算法的时间复杂度为O(n)。
源码
测试