中国剩余定理 CRT

中国剩余定理 CRT

正常版本CRT

要解的是一个很容易的东西
\[
\begin{aligned}
x\equiv a_1(mod\ m_1)\\
x\equiv a_2(mod\ m_2)\\
...\\
x\equiv a_n(mod\ m_n)
\end{aligned}
\]
保证\(m_1,m_2...m_n\)之间两两互质,求最小的\(x\)。

设\(M=\prod m_i\)。

首先我们确定一点,我们求出了任意一个满足条件的\(x\)之后,只需要对其模\(M\)就是最终的答案。

因为\(M\)是所有数的\(lcm\)。

考虑一下,对于每一个\(a_i\),如果我们能够求出一个数\(x_i\)

满足它是其他所有\(m\)的乘积,即\(M_i=M/m_i\)的倍数,并且\(x_i\equiv 1(mod\ m_i)\)

也就是对于任意一个\(x_i\),满足\(x_i\equiv 0(mod\ m_k),k\ne i\),\(x_i\equiv 1(mode\ m_i)\)

那么最终的答案就会是\(\sum(a_ix_i)mod\ M\)。

深思熟虑的考虑如何求出\(x_i\),

因为\(x_i\)是\(M_i\)的倍数,所以\(x_i=kM_i\equiv 1(mod\ m_i)\)

所以\(k\)是\(M_i\)在模\(m_i\)意义下的逆元。所以\(x_i\)就是\(k\)的\(M_i\)倍,注意最终统计入结果的模数是\(M\)。

所以,\(CRT\)的结果就是\(\sum (a_ik_iM_i)mod\ M\)。

不正常版本CRT

要求的东西同上,不保证所有\(m_i\)互质。

我们肯定不能像上面那样堆在一起求了。

换个方法,假设我们只有两个方程。\(x\equiv a_1(mod\ m_1),x\equiv a_2(mod\ m_2)\)

怎么算答案?

显然是要满足:\(x=x_1m_1+a_1=x_2m_2+a_2\),并且\(x\)最小。

显然是\(x_1,x_2\)都要尽可能的小。

所以\(x_1m_1+x_2m_2=a_2-a_1\)

那么\(exgcd\)可以求解最小的\(x_1\),然后就可以求得\(x=x_1m_1+a_1\)

这样子就可以同时满足这两个方程了,因为方程有多个,

所以我们把这两个方程合并,假设当前求出来的解是\(x'\)

那么我们就新加入一个方程\(x\equiv x'(mod\ lcm(m_1,m_2))\)就好了。

上一篇:在独立的文件里定义WPF资源


下一篇:WPF资源