Discrete Logging(POJ2417 + BSGS)

题目：
题意：
　　求一个最小的x满足a^x==b(mod p)，p为质数。
思路：
　　BSGS板子题，推荐一篇好的BSGS和扩展BSGS的讲解博客：http://blog.miskcoo.com/2015/05/discrete-logarithm-problem
代码实现如下：
  1 #include <set>
  2 #include <map>
  3 #include <queue>
  4 #include <stack>
  5 #include <cmath>
  6 #include <bitset>
  7 #include <cstdio>
  8 #include <string>
  9 #include <vector>
 10 #include <cstdlib>
 11 #include <cstring>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 
 16 typedef long long LL;
 17 typedef pair<LL, LL> pLL;
 18 typedef pair<LL, int> pli;
 19 typedef pair<int, LL> pil;;
 20 typedef pair<int, int> pii;
 21 typedef unsigned long long uLL;
 22 
 23 #define lson i<<1
 24 #define rson i<<1|1
 25 #define lowbit(x) x&(-x)
 26 #define bug printf("*********
");
 27 #define debug(x) cout<<"["<<x<<"]" <<endl;
 28 #define FIN freopen("D://code//in.txt", "r", stdin);
 29 #define IO ios::sync_with_stdio(false),cin.tie(0);
 30 
 31 const double eps = 1e-8;
 32 const int mod = 1e9 + 7;
 33 const int maxn = 1e6 + 7;
 34 const double pi = acos(-1);
 35 const int inf = 0x3f3f3f3f;
 36 const LL INF = 0x3f3f3f3f3f3f3f3f;
 37 
 38 int a, b, p;
 39 
 40 struct Hashmap { //哈希表
 41     static const int Ha=999917, maxe=46340;
 42     int E,lnk[Ha], son[maxe+5], nxt[maxe+5], w[maxe+5];
 43     int top, stk[maxe+5];
 44     void clear() {
 45         E=0;
 46         while(top) lnk[stk[top--]]=0;
 47     }
 48     void Add(int x,int y) {
 49         son[++E]=y;
 50         nxt[E]=lnk[x];
 51         w[E]=((1<<30) - 1) * 2 + 1;
 52         lnk[x]=E;
 53     }
 54     bool count(int y) {
 55         int x=y % Ha;
 56         for (int j = lnk[x]; j; j=nxt[j])
 57             if (y == son[j]) return true;
 58         return false;
 59     }
 60     int& operator [] (int y) {
 61         int x=y % Ha;
 62         for (int j = lnk[x]; j; j = nxt[j])
 63             if (y == son[j]) return w[j];
 64         Add(x,y);
 65         stk[++top]=x;
 66         return w[E];
 67     }
 68 }mp;
 69 
 70 int exgcd(int a, int b, int& x, int& y) {
 71     if(b == 0) {
 72         x = 1, y = 0;
 73         return a;
 74     }
 75     int d = exgcd(b, a % b, x, y);
 76     int t = x;
 77     x = y;
 78     y = t - a / b * y;
 79     return d;
 80 }
 81 
 82 int BSGS(int A, int B, int C) {
 83     if(C == 1) {
 84         if(!B) return A != 1;
 85         else return -1;
 86     }
 87     if(B == 1) {
 88         if(A) return 0;
 89         else return -1;
 90     }
 91     if(A % C == 0) {
 92         if(!B) return 1;
 93         else return -1;
 94     }
 95     int m = ceil(sqrt(C));  //分块
 96     int D = 1, base = 1;
 97     mp.clear();
 98     for(int i = 0; i <= m - 1; i++) {
 99         if(mp[base] == 0) mp[base] = i;
100         else mp[base] = min(mp[base], i);
101         base = ((LL)base * A) % C;
102     }
103     for(int i = 0; i <= m - 1; i++) {
104         int x, y, d = exgcd(D, C, x, y);
105         x = ((LL)x * B % C + C) % C;
106         if(mp.count(x)) return i * m + mp[x];
107         D = ((LL)D * base) % C;
108     }
109     return -1;
110 }
111 
112 int main() {
113     //FIN;
114     while(~scanf("%d%d%d", &p, &a, &b)) {
115         int ans = BSGS(a, b, p);
116         if(ans == -1) printf("no solution
");
117         else printf("%d
", ans);
118     }
119     return 0;
120 }