P1495 CRT,P4777 EXCRT

suxxsfe · 2020-03-15 21:50:25 · 个人记录

CRT

求解方程：

其中，保证m_i是两两互质的正整数，crt就是基于这个特征
我们记M=\prod_{i=1}^{n} m_i，和M_i=\dfrac{M}{m_i}，t_i满足M_it_i \equiv 1 \pmod {m_i}
即M_i是所有下标不为i的m乘起来，而t_i是M_i \bmod m_i的逆元
则对于任意的k\neq i，a_iM_it_i\equiv 0\pmod {m_k}，因为M_i中一定包含了m_k这个因数
而又因为M_it_i\equiv1\pmod{m_i}，所以a_iM_it_i\equiv a_i\pmod{m_i}
所以可以说明

为问题的一组解，且这个解在\mod M下唯一
当然通解就是x+kM,k\subset Z
当然求逆元的过程要用到exgcd，而题目要求最小正整数解，所以只要让解在[0,M-1]中就行了
但是，如果直接M=\prod_{i=1}^n m_i会乘爆，要让M=\text{LCM}_{i=1}^n m_i，可以有和上文叙述的一样的性质，下面的excrt也是一样
题目代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
    int x=0,y=1;
    char c=std::getchar();
    while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
    return y?x:-x;
}
int n;
LL a[15],m[15],M=1;
void exgcd(LL a,LL b,LL &x,LL &y){
    if(!b){
        x=1;y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    LL tmp=x;x=y;
    y=tmp-a/b*y;
}
int main(){
    n=read();
    for(reg int i=1;i<=n;i++){
        m[i]=read();a[i]=read();
        M=M/std::__gcd(M,m[i])*m[i];
    }
    LL ans=0,Mi,x,y;
    for(reg int i=1;i<=n;i++){
        Mi=M/m[i];
        exgcd(Mi,m[i],x,y);
        ans=((ans+Mi*x*a[i])%M+M)%M;
    }
    std::printf("%lld",ans);
    return 0;
}

EXCRT

还是求解方程：

但这次不保证m_i两两互质
不过这好像和CRT关系不大
考虑用数学归纳法，假设我们已知前i-1的解为ans，并记M=\text{LCM}_{k=1}^{i-1}m_k 则其通解为ans+M\times t

那么，我们就要确定一个t，使得ans+M\times t\equiv a_i\pmod {m_i}
然后新的ans=ans+M\times t
考虑求解上面那个同余方程的方法
因为exgcd可以求解方程ax+by=\gcd(a,b)
那么我们转变那个同余方程的形式：

那么如果\gcd(M,m_i)|(a_i-ans)，则有解，题目保证了有解
用exgcd求出的是：

那么让等式两边同时除以这个\gcd再同时乘以a_i-ans就行了

那我们要求的这个t就是t'+\dfrac{(a_i-ans)}{\gcd(M,m_i)}
注意在乘的时候会爆long long，要用int128或是龟速乘
我才不会告诉你们我快读不开long long见祖宗了
还有就是要通过ans=(ans+M)\bmod M来保证ans是正的
上代码，因为不开long long那事调了好长时间。。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline LL read(){
    LL x=0,y=1;
    char c=std::getchar();
    while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
    return y?x:-x;
}
int n;
LL a[100006],m[100006];
inline LL mul(LL n,LL k,LL mod){
    LL ans=0;
    while(k){
      if(k&1) ans=(ans+n)%mod;
      k>>=1;
      n=(n+n)%mod;
    }
    return ans;
}
LL exgcd(LL a,LL b,LL &x,LL &y){
    if(!b){x=1;y=0;return a;}
    LL ret=exgcd(b,a%b,x,y);
    LL z=x;x=y;y=z-(a/b)*y;
    return ret;
}
inline LL excrt(){
    LL x,y;
    LL M=m[1],ans=a[1];
    for(reg int i=2;i<=n;i++){
        LL b=((a[i]-ans)%m[i]+m[i])%m[i];
        LL gcd=exgcd(M,m[i],x,y);
        x=mul(x,b/gcd,m[i]);
        ans+=M*x;
        M*=m[i]/gcd;
        ans=(ans+M)%M;
    }
    return ans;
}
int main(){
    n=read();
    for(reg int i=1;i<=n;i++) m[i]=read(),a[i]=read();
    std::printf("%lld",excrt());
    return 0;
}

 
话说去年暑假在洛谷网校就学过一遍crt和excrt了
但当时就没怎么理解清楚，更写不出代码
这次是因为扩展卢卡斯要用到crt，才来写了一遍这两个题。。。