poj 2417 Discrete Logging (BSGS算法)

题目链接

题意:

Given a prime P, 2 <= P < 231, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that
BL == N (mod P)

思路:bsgs算法

详情见BSGS算法笔记

然后被map的count坑了一下? 我想判断map中某个key是否存在,用count会TLE,find也会TLE,[]可以通过….不太懂,复杂度不都是log吗,差常数?还是有人会退化?

不过似乎[]比较安全就对了。

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz