中国剩余定理
求方程组$x;equiv;a_i(mod;m_i)(iin[1,n])$的解$x$,其中$m_i$两两互质.
- 一般版本
令$M_i=prod_{j ot=i}m_j$,则$(M_i,m_i)=1$,所以存在$M_ix_i+m_iy_i=1$.
($x_i$为$M_i$在模$m_i$意义下的逆元)
令$e_i=M_ix_i$,则$e_iequivegin{cases}0(mod;m_j)&j ot=i\1(mod;m_j)&j=i\end{cases}$
所以$sum_{i=1}^{n}e_ia_i$是方程的一个解.
在$[0,prod_{i=1}^{n}m_i)$中只有唯一解,所以将求出的解对$prod_{i=1}^{n}m_i$取模即可.
- 闫神
记$q_{i,j}$表示$m_i$在模$m_j$意义下的逆元.
$xequivsum_{i=1}^{n}(a_i; imes;prod_{j=1}^{n}(m_j; imes;q_{j,i}))(mod;prod_{i=1}^{n}m_i)$
- 不互质
若要合并$x;equiv;a_i(mod;m_i),x;equiv;a_j(mod;m_j)$,
设$x=k_im_i+a_i=k_jm_j+a_j$,则$k_im_i-k_jm_j=a_j-a_i$.
用$exgcd$求出$k_i$(注意无解的情况),把两个方程合并为$x;equiv;k_im_i+a_i(mod;lcm(m_i,m_j))$.
lucas定理
求$c_n^m;mod;p$.
将$n,m$写成$p$进制:$n=a_0p^0; imes;a_1p^1; imes;...; imes;a_kp^k,m=b_0p^0; imes;b_1p^1; imes;...; imes;b_kp^k.$
则$C_{n}^{m};equiv;prod;C_{a_i}^{b_i}(mod;p)$.
所以$C_n^m;equiv;C_{n;mod;p}^{m;mod;p}; imes;C_{n/p}^{m/p}$
斐波那契数列
$fib(n+m)=fib(n+1); imes;fib(m)+fib(n); imes;fib(m-1).$
$gcd(fib(i),fib(j))=fib(gcd(i,j))$.