大步小步攻击算法_完全版
不错的大步小步算法,可以秒掉poj_2417, poj_3243这种题
struct hash{ int a, b, next;} Hash[MAXN << 1];int flg[MAXN + 66];int top, idx;void ins(int a, int b){ int k = b & MAXN; if (flg[k] != idx) { flg[k] = idx; Hash[k].next = -1; Hash[k].a = a; Hash[k].b = b; return; } while (Hash[k].next != -1) { if (Hash[k].b == b) return; k = Hash[k].next; } Hash[k].next = ++top; Hash[top].next = -1; Hash[top].a = a; Hash[top].b = b;} int find(int b){ int k = b & MAXN; if (flg[k] != idx) return -1; while (k != -1) { if (Hash[k].b == b) return Hash[k].a; k = Hash[k].next; } return -1;} int ex_gcd(int a, int b, int& x, int& y){ int t, ret; if (!b) { x = 1, y = 0; return a; } ret = ex_gcd(b, a % b, x, y); t = x, x = y, y = t - a / b * y; return ret;} int Inval(int a, int b, int n){ int x, y, e; ex_gcd(a, n, x, y); e = LL(x) * b % n; return e < 0 ? e + n : e;} int pow_mod(LL a, int b, int c){ LL ret = 1 % c; a %= c; while (b) { if (b & 1) ret = ret * a % c; a = a * a % c; b >>= 1; } return ret;} //A^x=B(mod C)//使用前先B%=Cint BabyStep(int A, int B, int C){ top = MAXN, ++idx; LL buf = 1 % C, D = buf, K; int i, tmp, d = 0; for (i = 0; i <= 100; buf = buf * A % C, ++i) if (buf == B) return i; while ((tmp = __gcd(A, C)) != 1) { if (B % tmp) return -1; ++d; C /= tmp, B /= tmp; D = D * A / tmp % C; } int M = (int)ceil(sqrt(C * 1.0)); for (buf = 1 % C, i = 0; i <= M; buf = buf * A % C, ++i) ins(i, buf); for (i = 0, K = pow_mod(LL(A), M, C); i <= M; D = D * K % C, ++i) { tmp = Inval((int)D, B, C); int w; if (tmp >= 0 && (w = find(tmp)) != -1) return i * M + w + d; } return -1;}