题解 P4454 【[CQOI2018]破解D-H协议】

先给出来啥叫离散对数问题吧…… 给出这个同余式 ## $X^{c}\equiv Y(modP)$ 现在已知X,Y,P求c，这就是离散对数问题 当然为了保证这个方程有唯一解，我们保证X是P的原根，所谓原根，就是对于任意的0<Y<P刚才的方程都有唯一解的X值了……，有一个推论是如果X是原根，那么$X^imodP(i∈(0,p))$刚好是1~p-1的一个全排列， 不过这和我们接下来讲的BSGS算法没有太大关系就是了，原根的存在只是为了保证离散对数问题解的唯一性就是了…… 对于离散对数问题来讲目前没有多项式算法(数论范畴认为只有$O(logN)$才算多项式算法，其他的例如$O(N)O(\sqrt{N})$是指数算法)，但是有一$O(\sqrt{N})$的分块算法，就是我们说的BSGS算法了 首先先考虑暴力 由于 $A^{p-1}\equiv 1(modP)$就是费马小定理，所以我们可以1~p-1的枚举c，然后判定$X^c$是否$modP$同余于$Y$，但是这样有点傻了……，所以我们考虑分块大法 我们令$bs=\sqrt{P-1}$然后将c用$c/bs$和$cmodbs$来表示c 现在我们枚举$c/bs$的值 那么现在的同余式变成了 ## $X^{cmodbs} \equiv Y×inv(X^{c/bs})(mod P)$ 我们现在需要快速查找$X^{cmodbs}$是否存在，发现这部分的指数最大不过bs，所以可以打表，用一个map存起来 我们发现$inv(X^{c/bs})$的值最多不过$(p-1)/bs$种所以也可以打表 然后求解离散对数的时候我们直接大力枚举c/bs然后每次到对应的map里去查有没有这个值就可以了，使用了map是因为我们得记一个这个值到底是$X$的多少次幂…… 所以所谓的BSGS不过是打了两个根号N的表的高端暴力而已 然后我们就暴力离散对数出a,b然后快速幂计算一发就可以了~ 上代码~