BSGS（Baby Steps,Giant Steps）算法详解

BSGS（Baby Steps,Giant Steps）算法详解

简介：

　　此算法用于求解 A^x≡B（mod C）；

　　由费马小定理可知；

　　x可以在O（C）的时间内求解；在x=c之后又会循环；

　　而BSGS（拔山盖世）算法可以在O（C^0.5）的时间内求解出；

内容：

　　主要运用分块的思想；

　　将 x=i*m-j，其中m=ceil（sqrt（C））；

　　A^（i*m-j）≡B（mod C）；

　　A^i*m/ A^j≡ B（mod C）；

　　A^i*m≡ B * A^j（mod C）；

　　枚举每个j（0<=j<=m），将B*A^j存入map；

　　再枚举每个i（0<=i<=m），判断A^i*m是否在map中存在值；

例题：

　　[SDOI2011]计算器　　题解见http://www.cnblogs.com/WQHui/p/7592381.html；

巴特西