BSGS

BSGS算法

BSGS算法
poj 2417
问题描述:
给定\(B\)、\(P\)、\(N\)。求使\(B^L \equiv N ( \% \ P)\)的最小\(L\)解。

首先,判断\(B\)和\(P\)互质,否则无解。
设\(x=im-j\),\(m=\left \lceil \sqrt{m} \right \rceil\)。那么问题可以化解成:\((a^m)^i \equiv ba^j ( \% P)\)。
只需要枚举\(i\),\(j\)即可。
先枚举\(j\in [0,m]\),记录\(ba^j\)和对应的最大的\(j\)。
枚举\(i\in [1,m]\),查询\((a^m)^i\)对应是否有,返回答案。