exgcd - crt

gcd

最大公约数(Hreatest Common Divisor)

欧几里得算法

$\gcd(a,b)=\gcd(b,a\mod b)$

可以通过反证法证明

int gcd(int a, int b) 
{
    if (b == 0) 
        return a;
    return gcd(b, a % b);
}

exgcd

用于接形如 $ax+by=\gcd(a,b)$ 的方程

$ax+by=\gcd(a,b)\\ 设 \begin{cases} ax_1+by_1=\gcd(a,b)\\ bx_2+(a \mod b)y_2=\gcd(b,a\mod b)\\ \end{cases}\\ \because \gcd(a,b)=\gcd(b,a\mod b)\\ \therefore ax_1+by_1=bx_2+(a\mod b)y_2\\ \therefore x_1=y_2,y_1=x_2-\left\lfloor\dfrac{a}{b}\right\rfloor y_2$

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

CRT

中国剩余定理 (Chinese Remainder Theorem, CRT)

解如下方程组

$\begin{cases} x \equiv a_1 \pmod {n_1}\\ x \equiv a_2 \pmod {n_2}\\ \cdots \\ x \equiv a_k \pmod {n_k}\\ \end{cases}$

令 $N=\prod \limits^{k}_{i=1} n_i$

对于第 $i$ 个方程

令

$m_i=\frac{N}{n_i}\\ c_i=m_i\cdot m_i^{-1}$

其中, $m_i$ 关于 $n_i$ 的逆元可以用 $exgcd$ 求得

方程组的解 $x\equiv \sum\limits^{k}_{i=1}a_ic_i \pmod N$

LL CRT(int k, LL* a, LL* r) 
{
    LL n = 1, ans = 0;
    for (int i = 1; i <= k; i++) 
        n = n * r[i];
    for (int i = 1; i <= k; i++) 
    {
        LL m = n / r[i], b, y;
        exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
        ans = (ans + a[i] * m * b % n) % n;
    }
    return (ans % n + n) % n;
}