有些东西特别爱忘，所以在这写一下。

EXCRT

首先会了 EXCRT 就可以不用会 CRT 了，感觉 EXCRT 或许好会。

有线性同余方程组：

\[\begin{cases} x\equiv& a_1\pmod {b_1}\\ x\equiv& a_2\pmod {b_2}\\ &\vdots\\ x\equiv& a_n\pmod {b_n}\\ \end{cases}\]

推导解法。

取出前两个式子，可以表示成：

\[x=k_1b_1+a_1=k_2b_2+a_2 \]

这样移项处理成：

\[b_1k_1-b_2k_2=a_2-a_1 \]

设 \(x_0=k1,y_0=k2\)，那么有：

\[b_1x_0-b_2y_0=a_2-a_1 \]

可以 exgcd 解出 \(x\)，注意是在 \(\dfrac{b_2}{\gcd(b_1,b_2)}\) 意义下的。

之后任意解可以写作 \(x_0+\dfrac{b_2}{\gcd(b_1,b_2)}\times k\)。

代回去：

\[x=b_1x_0+\dfrac{b_1b_2}{\gcd(b_1,b_2)}\times k+a_1 \]

改写后是：

\[x=b_1x_0+a_1+k\mathrm{lcm}(b_1,b_2) \]

于是合并成了：

\[x\equiv b_1x_0+a_1 \pmod{\mathrm{lcm}(b_1,b_2)} \]

~~讲真这个推导过程我学了快两年第一次看。~~

点击查看代码

inline ll mul(ll A,ll B,ll P){
    ll res=0;
    while(B){
        if(B&1) res=(res+A)%P;
        A=(A+A)%P;
        B>>=1;
    }
    return res;
}
ll exgcd(ll A,ll B,ll &X,ll &Y){
    if(!B){
        X=1,Y=0;
        return A;
    }
    ll D=exgcd(B,A%B,Y,X);
    Y-=A/B*X;
    return D;
}

int n;
ll a[maxn],b[maxn];

inline void EXCRT(){
    ll A=a[1],B=b[1];
    for(int i=2;i<=n;++i){
        ll X,Y;
        ll D=exgcd(B,b[i],X,Y),BD=b[i]/D;
        X=(X%BD+BD)%BD;
        X=mul(X,((a[i]-A)/D%BD+BD)%BD,BD);
        ll tmp=BD*B;
        A=(mul(X,B,tmp)+A)%tmp;
        B=tmp;
    }
    printf("%lld\n",A);
}

JZTXT

记

EXCRT