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} m_2,m_3,...,m_n \mid n_1\\ m_1,m_3,...,m_n \mid n_2\\ ... \\ m_1,m_2,...,m_{n-1} \mid n_n \end{cases} \]

因為所有 \(m\) 兩兩互質，所以只需要

\[M \div m_i \mid n_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 \]

這里的 \(M_i^{-1}\) 是 \(M_i\) 對于 \(m_i\) 的逆元，不能和 \(M_i\) 合并。

例題

CODE（點擊查看）

#include<bits/stdc++.h>
using namespace std;
#define llt long long
int n,m[12],a[12];

template<typename T>
inline void read(T &x){
    char s=getchar();x=0;bool pd=false;
    while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
    while('0'<=s&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
    if(pd) x=-x;
}
void exgcd(llt a,llt b,llt &x,llt &y){
	if(b==0) x=1,y=0;
	else exgcd(b,a%b,y,x),y-=a/b*x;
}

int main(){
	read(n);
	long long tm=1,ans=0;
	for(int i=1;i<=n;i++) read(m[i]),read(a[i]),tm*=m[i];
	for(int i=1;i<=n;i++){
		long long lm=tm/m[i],x,y;
		exgcd(lm,m[i],x,y);
		x=(x%m[i]+m[i])%m[i];
		ans=(ans+x*a[i]*lm)%tm;
	}
	printf("%lld",ans%tm);
}

這里推薦一篇博客，講的很細（我從那里學的，本文也有很多借鑒。

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（點擊查看）

#include<bits/stdc++.h>
using namespace std;
#define llt long long
__int128 n,na=0,nm=1;

template<typename T>
inline void read(T &x){
    char s=getchar();x=0;bool pd=false;
    while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
    while('0'<=s&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
    if(pd) x=-x;
}
llt gcd(llt a,llt b){return (b==0)?a:gcd(b,a%b);}
llt lcm(llt a,llt b){return a/gcd(a,b)*b;}
void exgcd(__int128 a,__int128 b,__int128 &x,__int128 &y){
	if(b==0) x=1,y=0;
	else exgcd(b,a%b,y,x),y-=a/b*x;
}
inline void hebing(llt a,llt m){
	llt sa=a-na;
	__int128 x,y;
	llt gd=gcd(nm,m);
	exgcd(nm,m,x,y);
	llt lm=m/gd;x*=(sa/gd),y*=(sa/gd);
	x=(x%lm+lm)%lm;
	na=na+nm*x;
	nm=lcm(nm,m);
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
	read(n);
	for(llt a,m,i=1;i<=n;i++) read(m),read(a),hebing(a,m);
	__int128 x,y;
	exgcd(1,nm,x,y);
	x=(x*na%nm+nm)%nm;
	long long ans=x; 
	printf("%lld",ans);
}

參考博客：http://www.rzrgm.cn/sparkyen/p/11432052.html

posted @ 2023-01-29 19:26 xrlong 閱讀(95) 評論(1) 收藏舉報

刷新頁面返回頂部

xrlong

博客密碼是 K8 色號

CRT&EXCRT（中國剩余定理和擴展中國剩余定理）

CRT:

用途：

具體方法：

公式：

例題

EXCRT

例題

公告

Loading