标签: BSGS

2 篇文章

BZOJ4128 Matrix矩阵BSGS模板题
题面 给定矩阵A,B和模数p,求最小的x满足 A^x = B (mod p) 思路 一眼看去就是BSGS,很显然这个结论在矩阵中也同样适用,那么把乘法替换成矩阵乘法然后矩阵HASH判重即可。(就这么简单) 代码 #include<bits/stdc++.h> #define LL long long #define Mod 998244353…
BSGS学习小结
1.BSGS 求解如关于$x$的方程$A^x≡B \mod\ p$ 的最小整数解。$(A,p互质,p为质数)$ 不难发现$x<=p$ 因为会出现循环。 靠虑将$x$分解为$i\times sqrt(p)-j$ 。 则原式化为$A^{i\times \lceil sqrt(p)\rceil}\times A^{-j}≡B \mod\ p$ 对$…