数学小算法
exgcd
[x = y \ y = t - a /b imes y
]
CRT
[ans = sum_{i = 1}^n{b_i imes M_i imes 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) \ xequiv 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 imes m_1(mod lcm(m_1, m_2))
]
依次合并就可以了
BSGS
[求解方程y^xequiv z (mod p) gcd(y, p) = 1
]
设(x = am-b)
[y^{am}equiv z imes y^b
]
由费马小定理(a^pequiv 1(mod p))
知(am <= p)即可
所以当(m = ceil(sqrt p))时取最低复杂度，两边暴力枚举即可。