给出n条形如 x≡ai(modmi) x ≡ a i ( mod m i ) ，那么你现在需要解出x。
我们现在来考虑一种比较简单的情况：各个方程的m都是互质的，那么我们如果有一个 x=∑ni=1f(i) x = ∑ i = 1 n f ( i ) 满足 f(i)%mi=ai,f(i)%aj,(j!=i)=0 f ( i ) % m i = a i , f ( i ) % a j , ( j ! = i ) = 0 ，那么这个x就是一个满足条件的解了。 我们来构造一下，记 M=Πmi M = Π m i
f(i)=Mmi∗((Mmi)−1%mi)∗ai f ( i ) = M m i ∗ ( ( M m i ) − 1 % m i ) ∗ a i 假设m不互质怎么办呢？没关系我们可以考虑合并方程。 对于 x≡a1(modm1),x≡a2(modm2) x ≡ a 1 ( mod m 1 ) , x ≡ a 2 ( mod m 2 ) ，则 x=a1+m1k1=a2+m2k2 x = a 1 + m 1 k 1 = a 2 + m 2 k 2 经过一阵子推导我们可以得到 x≡a1+m1cd(m1d)−1(这里的逆元是关于m2d的)(modm1m2d)(c=a2−a1,d=(m1,m2)) x ≡ a 1 + m 1 c d ( m 1 d ) − 1 ( 这 里 的 逆 元 是 关 于 m 2 d 的 ) ( mod m 1 m 2 d ) ( c = a 2 − a 1 , d = ( m 1 , m 2 ) )p是素数，则C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p
设 p=qe p = q e (q是素数，结合中国剩余定理即可处理任意模数) 组合数可以表示成阶乘和阶乘逆元的乘积，所以我们只要考虑如何表示阶乘。设 n!=qk(n)v(n) n ! = q k ( n ) v ( n ) ，其中vn与q互质。 阶乘n!可以表示成前n个连续正整数1,2,⋯,n的乘积，将这n个数中与q互质的数提取出来，这一部分的数乘积累积给v(n)。而不互质的数必然是q,2⋅q,⋯, ⌊n/q⌋∗q ⌊ n / q ⌋ ∗ q ，每个数字提取一个q，则至少可以提取出⌊n/q⌋个q累加给k(n)。那么剩下没考虑的数字就是1,2,⋯, ⌊n/q⌋ ⌊ n / q ⌋ 也即 ⌊n/q⌋! ⌊ n / q ⌋ ! ，再次重复上述过程进行提取即可。 复杂度是O( qe q e +log n)
