目录

• 扩展欧几里得
• 中国剩余定理

扩展欧几里得

求解同余方程$a\times x \equiv c (mod b) $

\(exgcd\)用于\(a,c\)互质情况下，两边（包括模数）需要同除以\(gcd\)

特解：\(exgcd\)的返回值\(\times c/gcd\)

通解：\(x+i \times (b/gcd)\)

无解：根据裴蜀定理，若\(c%gcd \neq 0\)则无解

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b) { x=1; y=0; return a; }
    ll d=exgcd(b,a%b,x,y);
    ll t=x; x=y; y=t-a/b*y;
    return d;
}

中国剩余定理

求解方程组\(x \equiv a_i,(mod m_i)\)

令\(M=\prod{m_i}\)，\(M_i=M/m_i\)，\(M_it_i \equiv 1 ,(mod m_i)\)

特解：\(ans=\Sigma{a_im_it_i}\)

通解：\(ans+i\times M\)