知识点简单总结——BSGS与EXBSGS
BSGS
给出 $ A,B,C,(A,C)=1 $ ，要你求最小的 $ x $ ，使得 $ A^x equiv B(mod C) $ 。
在数论题中经常会看见这样的式子，而它的用处确实也不少，例如：
求指标
。。。想不到了（被打）
解题思路
众所周知 $ A^{x} equiv A^{x mod phi (C) }(mod C) $
所以考虑暴力枚举就可以。
但是我们显然要考虑一个更快的。
分块就好了。
设块大小 $ m $ ，预处理出 $ A^{1,2,...,m-1} $ 扔进哈希表。
剩下的应该不难了，经典分块一般的操作。
枚举每一个 $ i $ ,左式 $ =A^{im} $ 时哈希表里是否存在一个值 $ z $ 使得 $ A^{im}*z equiv B(mod C) $ ，存在的话就返回该最小答案。
EXBSGS
同上，唯一变化就是不保证 $ (A,C)=1 $ 。
既然它不给保证那就我们自己让它转化成 $ (A,C)=1 $ 。
对于 $ A^x equiv B(mod C),(A,C)=d $ ，直接全都除以 $ d $ ，
（如果 $ B mod d eq 0 $ 直接无解）
变成 $ (A/d)*A^{x-1} equiv B/d(mod C/d) $ 。
此时仍然无法保证 $ A $ 与 $ C/d $ 互质，
那么就重复以上操作直到互质。
然后就没了。