〔Fancy Zone〕中国剩余定理与BSGS
题单介绍
# 
**一、中国剩余定理（Chinese Remainder Theorem）**
中国剩余定理，又称孙子定理，是数论中的一个重要定理。
它表述为：设正整数 $m_1, m_2, \cdots, m_n$ 两两互质，$M = m_1 \times m_2 \times \cdots \times m_n$ ，$M_i = \frac{M}{m_i}$ ，则同余方程组：
$$\begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\cdots \\
x \equiv a_n \pmod{m_n}
\end{cases}$$
在模 $M$ 意义下有唯一解 $x \equiv a_1 M_1 y_1 + a_2 M_2 y_2 + \cdots + a_n M_n y_n \pmod{M}$ ，其中 $M_i y_i \equiv 1 \pmod{m_i}$ 。
例如：有同余方程组 $\begin{cases}
x \equiv 2 \pmod{3} \\
x \equiv 3 \pmod{5} \\
x \equiv 2 \pmod{7}
\end{cases}$
首先，$m_1 = 3$，$m_2 = 5$，$m_3 = 7$，$M = 3 \times 5 \times 7 = 105$ 。
$M_1 = \frac{105}{3} = 35$，求解 $35y_1 \equiv 1 \pmod{3}$，可得 $y_1 = 2$ 。
$M_2 = \frac{105}{5} = 21$，求解 $21y_2 \equiv 1 \pmod{5}$，可得 $y_2 = 1$ 。
$M_3 = \frac{105}{7} = 15$，求解 $15y_3 \equiv 1 \pmod{7}$，可得 $y_3 = 1$ 。
则解为 $x \equiv 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 \equiv 23 \pmod{105}$ 。
**二、BSGS（Baby Step Giant Step）**
BSGS 算法主要用于求解形如 $a^x \equiv b \pmod{p}$ 的离散对数问题。
基本思想是将指数 $x$ 分为两部分，即 $x = im - j$ ，其中 $m = \lceil\sqrt{p}\rceil$ 。
首先计算出所有 $a^j \pmod{p}$ （$0 \leq j < m$），并存储在一个哈希表中。
然后对于 $i = 0, 1, 2, \cdots, m - 1$ ，计算 $b \times (a^{-m})^i \pmod{p}$ ，在哈希表中查找是否存在对应的 $a^j$ 。
例如：求解 $2^x \equiv 3 \pmod{7}$ 。
取 $m = \lceil\sqrt{7}\rceil = 3$ 。
计算 $2^0 \equiv 1 \pmod{7}$ ，$2^1 \equiv 2 \pmod{7}$ ，$2^2 \equiv 4 \pmod{7}$ 。
然后计算 $3 \times 2^{-3} \equiv 3 \times 4 \equiv 5 \pmod{7}$ ，未在哈希表中找到。
计算 $3 \times (2^{-3})^2 \equiv 3 \times 2 \equiv 6 \pmod{7}$ ，未在哈希表中找到。
计算 $3 \times (2^{-3})^3 \equiv 3 \times 1 \equiv 3 \pmod{7}$ ，在哈希表中找到对应的 $2^1$ ，所以 $x = 3 \times 3 - 1 = 8$ 。
---
###### *题单贡献者：*
###### *题目编排：[djxstc](https://www.luogu.com.cn/user/1020627)*
###### *笔记补充：[BunDragon126](https://www.luogu.com.cn/user/927203)*
###### 中国剩余定理与BSGS笔记 © Fancy Zone OI 版权所有 | 感谢上方贡献人员！