中国剩余定理

给定k个互质的m1,m2,—,mk,以及n个a1,a2,—,ak . 从而得到k个线性同余方程(x%m1==a1) .中国剩余定理就是用来求解x的

关于逆元定义:逆元存在的充要条件是a与M互质,则一定存在唯一的x使得a*x % M ==1,此时的x称为a的逆元,逆元的求法:

1.扩展欧几里得求,可以将逆元的模方程转化为一个普通方程，即ax+My==1,通过扩欧可以求出一个x的特解，mod M 即为最小正解
2.特殊情况，费马小定理，如果a与M互质，并且M为质数的话，通过费马小定理可以知道a^m-1 mod M == 1,所以x即为a^m-2

逆元的作用:在模运算中，直接进行除法运算会错误，例如:(a/b mod m != a mod m / b mod m) , 因此就需要用到逆元，a/b mod m == a*b^-1 mod m

记M = m1m2—*mk , Mi = M/mi , 容易知道Mi和mi互质，所以一定存在Mi在mod mi下的逆元Mi^-1

x = a1M1M1^-1 + a2M2M2^-1···· + akMkMk^-1 , 可以通过代入同余方程组验证,比如第一个式子，代入x,M1*M1^-1在mod m1下为1，而后面几项都含有因子m1，所以mod m1 == 0

关于取模的位置:加减乘法运算：对于仅包含加、减、乘的式子，每次运算后立即对模数

M取模，最终结果与直接对整个式子取模的结果一致。(也就是说不需要管可不可以取模，觉得数大了就取模就对了)