exgcd

\[x = y \ \\ y = t - a /b \times y \]

CRT

\[ans = \sum_{i = 1}^n{b_i\times M_i\times inv(M_i,mod_i)} \]
\[M_k=(\prod_{i=1}^n {} mod_i)/mod_k \]
\[inv(M_i, mod_i)表示M_i在模mod_i意义下的逆元 \]

EXCRT

原理：合并同余方程
对于 两个同余方程

\[x \equiv r_1(mod \ m_1) \\ x\equiv r_2(mod\ m_2) \]

有

\[k_1m_1-k_2m_2=r_2-r_1 \]

显然可以解出\(k_1, k_2\),然后则有:

\[x \equiv r_1 + k_1 \times m_1(mod\ lcm(m_1, m_2)) \]

依次合并就可以了

BSGS

\[求解方程y^x\equiv z (mod\ p) \ \ gcd(y, p) = 1 \]

设\(x = am-b\)

\[y^{am}\equiv z \times y^b \]

由费马小定理\(a^p\equiv 1(mod \ p)\)
知\(am <= p\)即可
所以当\(m = ceil(\sqrt p)\)时取最低复杂度，两边暴力枚举即可。