excrtexgcd_算法

void exgcd(ll a,ll b,ll &x,ll &y) {
    if(!b) return x=1,y=0,void();
    exgcd(b,a%b,x,y);tie(x,y)=mp(y,x-a/b*y);
}
ll inv(ll a,ll p) {
    ll x,y;exgcd(a,p,x,y);
    return (x%p+p)%p;
}
pii crt(ll a1,ll b1,ll a2,ll b2) {
    return mp(a1*a2,(a2*inv(a2,a1)*b1+a1*inv(a1,a2)*b2)%(a1*a2));
}

excrt：

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
pii exgcd(ll a,ll b) {
    if(!b) return {1,0};
    auto[x,y]=exgcd(b,a%b);
    return {y,x-a/b*y};
}
pii excrt(pii o1,pii o2) {
    auto[a1,m1]=o1;auto[a2,m2]=o2;
    ll g=gcd(m1,m2),l=m1/g*m2;
    auto[l1,l2]=exgcd(m1/g,m2/g);
    return {(a1+(a2-a1)/g*l1*m1)%l,l};
}

$\rm excrt$ 推法：

我们要合并 $x\equiv a_1\pmod {m_1}\equiv a_2\pmod{m_2}$。

先把同余式变成标准形式：$x=a_1+k_1m_1=a_2+k_2m_2$，移项得 $k_1m_1-k_2m_2=a_2-a_1$，判完无解后利用 $\rm exgcd$ 求出 $k_1,k_2$，即可求出 $x$。

$\rm exgcd$ 推法：

给定 $(a,b)$，我们需要求出满足 $xa+yb=\gcd(a,b)$ 的一组 $(x,y)$。

设 $c=a\bmod b$，现在假设我们已知 $ub+vc=\gcd(a,b)$ 的一组 $(u,v)$，试图推出 $(x,y)$。

显然 $c=a-[\frac a b]b$，代入，$ub+va-v[\frac a b]b=\gcd(a,b)$，$va+(u-v[\frac a b])b=\gcd(a,b)$，即 $(x,y)=(v,u-v[\frac a b])$。

代码里记得写 u-a/b*v，因为要下取整。