夢に僕らで帆を張って
来るべき日のために夜を超え

标签 同余 下的文章

September 26, 2019

中国剩余定理&扩展中国剩余定理

中国剩余定理一、中国剩余定理(CRT)求解同余方程组$$ \left\{ \begin{aligned} & x \equiv a_1 \ (\bmod \ m_1) \\ & x \equiv a_2 \ (\bmod \ m_2) \\ & \dots \\ & x \equiv a_n \ (\bmod \ m_n...
September 26, 2019

BSGS算法

BSGS(Baby Step Giant Step)算法一、BSGS算法求解高次同余方程$$A^x \equiv B \ (\bmod \ C)$$其中 $(A,C)=1$1.求解令 $x=im+j$此时方程转化为$$A^j \equiv B \cdot A^{-im} \ (\bmod \ C)$$首先对 $i \in [1,m-1]$ ,计算出 $A^i \% C$ 并将其存入hash表...