中国剩余定理

求方程组$x\;\equiv\;a_i(mod\;m_i)(i\in[1,n])$的解$x$,其中$m_i$两两互质.

• 一般版本

令$M_i=\prod_{j\not=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_i\equiv\begin{cases}0(mod\;m_j)&j\not=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$意义下的逆元.

$x\equiv\sum_{i=1}^{n}(a_i\;\times\;\prod_{j=1}^{n}(m_j\;\times\;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\;\times\;a_1p^1\;\times\;...\;\times\;a_kp^k,m=b_0p^0\;\times\;b_1p^1\;\times\;...\;\times\;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}\;\times\;C_{n/p}^{m/p}$

斐波那契数列

$fib(n+m)=fib(n+1)\;\times\;fib(m)+fib(n)\;\times\;fib(m-1).$

$gcd(fib(i),fib(j))=fib(gcd(i,j))$.