POJ 2417 Discrete Logging（离散对数-小步大步算法）

Description

Given a prime P, 2 <= P < 2³¹, 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

 == N (mod P)

Input

Read several lines of input, each containing P,B,N separated by a space.

Output

For each line print the logarithm on a separate line. If there are several, print the smallest; if there is none, print "no solution".

题目大意：求离散对数，B^L = N (mod P)，其中P是素数，求L。

思路：大步小步算法的模板题。

PS：白书上的模板少了个ceil向上取整……

PS：用map来哈希TLE了。速度和手写哈希原来差距这么大……

代码（47MS）：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 const int SIZEH = 65537;
10 
11 struct hash_map {
12     int head[SIZEH], size;
13     int next[SIZEH];
14     LL state[SIZEH], val[SIZEH];
15 
16     void init() {
17         memset(head, -1, sizeof(head));
18         size = 0;
19     }
20 
21     void insert(LL st, LL sv) {
22         LL h = st % SIZEH;
23         for(int p = head[h]; ~p; p = next[p])
24             if(state[p] == st) return ;
25         state[size] = st; val[size] = sv;
26         next[size] = head[h]; head[h] = size++;
27     }
28 
29     LL find(LL st) {
30         LL h = st % SIZEH;
31         for(int p = head[h]; ~p; p = next[p])
32             if(state[p] == st) return val[p];
33         return -1;
34     }
35 } hashmap;
36 
37 LL inv(LL a, LL n) {
38     if(a == 1) return 1;
39     return ((n - n / a) * inv(n % a, n)) % n;
40 }
41 
42 LL pow_mod(LL x, LL p, LL n) {
43     LL ret = 1;
44     while(p) {
45         if(p & 1) ret = (ret * x) % n;
46         x = (x * x) % n;
47         p >>= 1;
48     }
49     return ret;
50 }
51 
52 LL BabyStep(LL a, LL b, LL n) {
53     LL e = 1, m = LL(ceil(sqrt(n + 0.5)));
54     hashmap.init();
55     hashmap.insert(1, 0);
56     for(int i = 1; i < m; ++i) {
57         e = (e * a) % n;
58         hashmap.insert(e, i);
59     }
60     LL v = inv(pow_mod(a, m, n), n);
61     for(int i = 0; i < m; ++i) {
62         LL t = hashmap.find(b);
63         if(t != -1) return i * m + t;
64         b = (b * v) % n;
65     }
66     return -1;
67 }
68 
69 int main() {
70     LL p, b, n;
71     while(cin>>p>>b>>n) {
72         LL ans = BabyStep(b, n, p);
73         if(ans == -1) puts("no solution");
74         else cout<<ans<<endl;
75     }
76 }

View Code