CRT&EXCRT(中国剩余定理和扩展中国剩余定理)

  • 阿里云国际版折扣https://www.yundadi.com

  • 阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6
    公式,推导,有点板子题

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

    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(点击查看)
    #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);
    }
    

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

  • 阿里云国际版折扣https://www.yundadi.com

  • 阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6

    “CRT&EXCRT(中国剩余定理和扩展中国剩余定理)” 的相关文章