526互联

浅谈同余2(扩展欧几里得，中国剩余定理，BSGS)

发布时间 2023-05-21 12:59:48作者: xuyiyang

上一篇：$浅谈同余1(常用定理和乘法逆元)$

(https://www.cnblogs.com/xyy-yyds/p/17418458.html)

下一篇:  $浅谈同余3(扩展中国剩余定理，扩展BSGS)$

(https://www.acwing.com/blog/content/34866/)

0x20 扩展欧几里得 $O(\log(a + b))$
裴蜀定理:
对于任意一对整数$a, b$, 存在一对整数$x, y$, 满足$ax+by=\gcd(a, b)$

证明:
在欧几里得算法的最后一步时，$b=0, \gcd(a, 0) = a$, 显然$x = 1, y = 0$
若$b>0$, 则$\gcd(a, b) = \gcd(b, a \bmod b)$,假设存在一对整数$x, y$, 满足$bx + (a \bmod b)y = bx + (a - b\lfloor a / b \rfloor)y = ay - b(x - \lfloor a / b \rfloor y)$, 所以令$x ^ \prime = y, y ^ \prime = x - \lfloor a / b \rfloor y$, 就得到了$ax^\prime+by^\prime=\gcd(a, b)$
证毕, $x, y$的计算方法就是扩欧的计算方式
$Code$:

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    
    int d = exgcd(b, a % b, y, x); //y, x传好算
    
    y -= a / b * x;
    
    return d;
}

扩展欧几里得解线性同余方程

求$a \times x \equiv b \pmod m$的一组解$x$

$a \times x = b + m \times y$
设$y ^ \prime$为$-y$
$a \times x + y ^ \prime \times m = b$
直接扩欧求出$\gcd(a, m)$的解后，把$x$扩大$b / \gcd(a, m)$倍即可，然后取模
有解仅当$\gcd(a, m) | b$
$Code$:

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, y, x);

    y -= a / b * x;

    return d;
}

int d = exgcd(a, m, x, y);

if (b % d) puts("impossible");
else printf("%d\n", (long long)b / d * x % m);

 

0x30 中国剩余定理 $O(n \log V), V = \max \limits _ {i = 1} ^ n {\max{a_i, m_i}}$
设$m_1, m_2, m_3, ..., m_n$两两互质, $m = \prod \limits _ {i = 1} ^ n m_i, M_i = m / m_i, t_i$是线性同余方程$M_i t_i \equiv 1 \pmod {m_i}$的一个解。对于任意的$n$个整数$a_1, a_2, a_3, ..., a_n$, 方程组
$$
\begin{cases}
x \equiv {a_1} \pmod {m_1} \\\
x \equiv {a_2} \pmod {m_2} \\\
x \equiv {a_3} \pmod {m_3} \\\
...\\\
x \equiv {a_n} \pmod {m_n} \\\
\end{cases}
$$

用整数解，解为$x = \sum \limits _ {i = 1} ^ n {a_i M_i t_i}$ (摘自《算法竞赛进阶指南》)

$Code$:

void exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return ;
    }

    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

int main() {
    scanf("%d", &n);

    M = 1;
    for (int i = 1; i <= n; i ++ ) scanf("%d %d", m + i, a + i), M *= m[i];

    for (int i = 1; i <= n; i ++ ) {
        ll Mi = M / m[i];

        ll ti, y;
        exgcd(Mi, m[i], ti, y);

        res += a[i] * Mi * ti;
    }

    printf("%lld", (res % M + M) % M);

    return 0;
}

0x40 BSGS算法(Baby Step, Giant Step) $O(\sqrt m)$

解高次同余方程$a^x \equiv \pmod m$的最小整数解

设$x = i \times t - j$, 其中$t = \lceil \sqrt m \rceil, 0 \le j \le t - 1$, 则方程变成$a^{i \times t - j} \equiv b \pmod m$,即$a^{t ^ i} \equiv b \times a ^ j \pmod m$
对于所有$j$, 把$a^j \times b \bmod m$插入$Hash$
然后枚举$i$,判断即可

$Code$:

int baby_step_giant_step(int a, int b, int p)
{
    map<int, int> hash;
    hash.clear();
    
    b %= p;
    int t = (int)sqrt(p) + 1;
    for (int i = 0; i < t; i ++ )
    {
        int val = (LL)b * qmi(a, i, p) % p;
        hash[val] = i;
    }
    a = qmi(a, t, p);
    if (!a) return !b ? 1 : -1;
    for (int i = 0; i <= t; i ++ )
    {
        int val = qmi(a, i, p);
        int j = hash.find(val) == hash.end() ? -1 : hash[val];
        if (j >= 0 && i * t - j >= 0) return i * t - j;
    }
    return -1;
}