最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

全球最资讯丨CRT&EXCRT（中国剩余定理和扩展中国剩余定理）

来源：博客园

稍微难一点，其实也挺简单。

CRT:

用途：

给定一个同余方程组，保证所有 \(m\) 两两互质:

\[\begin{cases} x\equiv a_1\pmod{m_1} \\ x\equiv a_2\pmod{m_2} \\ ... \\ x\equiv a_n\pmod{m_n}\end{cases}\]

用于求其解。


【资料图】

具体方法：

自我感觉叫方法好一点，建议理解记忆，公式见下。首先我们先找一组数 \(n\) ,使得：

\[n_i \bmod m_i = a_i \text{ 或者说 }n_i\equiv a_i\pmod{m_i}\]

因为：如果 \(a \bmod b = t\) 那么 \((a+k\times b) \bmod b = t\) （比较显然所以：如果 \(m_1 \mid n_2\) 那么 \((n_1 + n_2) \bmod m_1 = a_1\)如果 \(m_2 \mid n_1\) 那么 \((n_1 + n_2) \bmod m_2 = a_2\)也就是说，要想使

\[\begin{cases} n_1 + n_2\equiv a_1\pmod{m_1} \\ n_1 + n_2\equiv a_2\pmod{m_2}\end{cases}\]

只需要

\[\begin{cases} m_1 \mid n_2 \\ m_2 \mid n_1 \end{cases}\]

同理，我们设 \(sum=\sum\limits_{i=1}^nn_i,M=\prod\limits_{i=1}^nm_i\) 要想使：

\[\begin{cases} sum\equiv a_1\pmod{m_1} \\ sum\equiv a_2\pmod{m_2} \\ ... \\ sum\equiv a_n\pmod{m_n}\end{cases}\]

只需要

\[\begin{cases} n_1 \mid m_2,m_3,...,m_n\\ n_2 \mid m_1,m_3,...,m_n \\ ... \\ n_n \mid m_1,m_2,...,m_{n-1}\end{cases}\]

因为所有 \(m\) 两两互质，所以只需要

\[n_i \mid M \div m_i\]

接下来考虑怎么求 \(n_i\)我们设 \(n_i=M\div m_i \times t_i\)于是我们只需求一个 \(t_i\) ，使其满足

\[M\div m_i \times t \equiv a_i\pmod{m_i}\]

因为 \(M\div m_i\) 是个常数，所以直接用 \(exgcd\)求解即可。当然也可以先用乘法逆元算 \(M\div m_i \times t \equiv 1\pmod{m_i}\) 在乘上 \(a_i\) ，本质相同。

这样我们就可以求出所有 \(n_i\) ，进而求出 \(x=\sum\limits_{i=1}^nn_i\)，如果 \(x\) 要求最小，只需要 \(\bmod M\) 即可。

公式：

设 \(M=\prod\limits_{i=1}^nm_i,M_i=M \div m_i\)则

\[x=\sum\limits_{i=1}^n a_i \times M_i \times M_i^{-1} \bmod M\]

例题

CODE（点击查看）
#includeusing namespace std;#define llt long longint n,m[12],a[12];templateinline void read(T &x){    char s=getchar();x=0;bool pd=false;    while(s<"0"||"9"

这里推荐一篇博客，讲的很细（我从那里学的，本文也有很多借鉴。

EXCRT

其实和 \(crt\) 没有什么关联，单纯推式子。我们来看一下同余方程组

\[\begin{cases} x\equiv a_1\pmod{m_1} \\ x\equiv a_2\pmod{m_2} \\ ... \\ x\equiv a_n\pmod{m_n}\end{cases}\]

这里不保证 \(m\) 互质首先看第一二个式子：

\[\begin{cases} x\equiv a_1\pmod{m_1} \\ x\equiv a_2\pmod{m_2}\end{cases}\]

变形得到：

\[\begin{cases} x = a_1 + m_1k_1 \\ x = a_2 + m_2k_2\end{cases}\]\[\therefore a_1+m_1k_1=a_2+m_2k_2\]

整理：

\[m_1k_1-m_2k_2=a_2-a_1\]

运用 \(exgcd\) 解得 \(k_1\) 的一组解：

\[k_1=r\]\[\therefore k_1 \text{ 的通解为 } k_1=r+\frac{m_2}{\gcd(m_1,m_2)} \times t \mid t \in Z\]

将上式带入 \(x = a_1 + m_1k_1\) 得：

\[x=a_1+m_1r+\frac{m_1m_2}{\gcd(m_1,m_2)}\times t\]\[\because \operatorname{lcm(m_1,m_2)}=\frac{m_1m_2}{\gcd(m_1,m_2)}\]\[\therefore x=a_1+m_1r+\operatorname{lcm(m_1,m_2)}\times t\]

变形得到：

\[x\equiv a_1+m_1r\pmod{\operatorname{lcm(m_1,m_2)}}\]

于是我们就成功将两个同余方程化简成了一个。同理化简下去直到一个，求解即可。

例题

CODE（点击查看）
#includeusing namespace std;#define llt long long__int128 n,na=0,nm=1;templateinline void read(T &x){    char s=getchar();x=0;bool pd=false;    while(s<"0"||"9"

参考博客：https://www.cnblogs.com/sparkyen/p/11432052.html

关键词： 中国剩余定理 点击查看 于是我们