hdu 2815 Mod Tree (扩展BSGS算法)

题意:k^D=n(%p),求最小的D  (1<=K, P, N<=10^9)

思路:出题人英文水平捉鸡。。。。

扩展BSGS算法即可,注意p>=n的时候显然是无解的,判掉。

 

BZOJ 2480: Spoj3105 Mod (扩展BSGS算法,模板)

Description

已知数a,p,b,求满足a^x≡b(mod p)的最小自然数x。

Input

    每个测试文件中最多包含100组测试数据。
    每组数据中,每行包含3个正整数a,p,b。
    当a=p=b=0时,表示测试数据读入完全。

Output

    对于每组数据,输出一行。
    如果无解,输出“No Solution”(不含引号),否则输出最小自然数解。

Sample Input

5 58 33
2 4 3
0 0 0

Sample Output

9
No Solution

HINT

  100%的数据,a,p,b≤1e9。
2016.3.29新加数据一组 by  1430586275

 

思路:BSGS算法,需要注意这里没有保证(a,p)=1,因此不能直接使用BSGS算法。

我们称之为扩展BSGS算法…

但是其实并不是什么新东西,不过是几次gcd,将条件转化成满足BSGS算法的情况

 

BSGS(Baby steps giant steps)算法学习笔记

离散对数(Discrete Logarithm)问题是这样一个问题,它是对于模方程

a^x=b(mod prime),求满足条件的X,或者得出不存在这样的X

最暴力的思路,那么就是枚举x? 根据费马小定理,只需要枚举[0,p-1)

但是还是很大…我们不禁想到把x写成x=A*m+B的形式,m=ceil(sqrt(p))

因此有 a^{A\lceil \sqrt{p} \rceil + B} \equiv b \pmod p ,变形得到 a^{A\lceil \sqrt{p} \rceil} \equiv b\cdot a^{-B} \pmod p

然后预处理一边存到map中,从小到大枚举另一边看是否存在…

 

我们可以设 x=A \lceil \sqrt{p} \rceil - B,其中 0 \leq B < \lceil \sqrt{p} \rceil,  0 < A \leq \lceil \sqrt{p} \rceil + 1,这样的话化简后的方程就是

 a^{A\lceil \sqrt{p} \rceil} \equiv b\cdot a^B \pmod p

就可以不用求出逆元,要注意只是不用求出逆元,而不是没有用到逆元的存在

就可以不用求出逆元,要注意只是不用求出逆元,而不是没有用到逆元的存在

就可以不用求出逆元,要注意只是不用求出逆元,而不是没有用到逆元的存在

 

其实在m=sqrt(p)的时候你可能就有预感了…

BSGS算法的本质,就是个分块啊,而分块的本质就是暴力乱搞…所以BSGS看起来很高大上的算法不过是暴力乱搞2333

而BSGS的名字也很贴切…A的变化是giant step?B的变化是baby step? (纯属yy…但是我感觉这样想很好理解啊?

需要注意的是,这里介绍的是常规的BSGS算法,

前提条件是a和P互质

前提条件是a和P互质

前提条件是a和P互质

放一个板子好了,poj 2417

 

参考资料:

一个很多BSGS算法初学者的误区

扩展大步小步法解决离散对数问题

大步小步算法与扩展大步小步算法

BSGS算法学习小记(大步小步算法)

 

 

 

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吗,差常数?还是有人会退化?

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