POJ 3243 Clever Y（离散对数-拓展小步大步算法）

Description

Little Y finds there is a very interesting formula in mathematics:

X^Y mod Z = K

Given X, Y, Z, we all know how to figure out K fast. However, given X, Z, K, could you figure out Y fast?

Input

Input data consists of no more than 20 test cases. For each test case, there would be only one line containing 3 integers X, Z, K (0 ≤ X, Z, K ≤ 10⁹).
Input file ends with 3 zeros separated by spaces.

Output

For each test case output one line. Write "No Solution" (without quotes) if you cannot find a feasible Y (0 ≤ Y < Z). Otherwise output the minimum Y you find.

题目大意：求离散对数。没有保证Z一定是素数。

思路：http://blog.csdn.net/ivan_zjj/article/details/7597109

PS：说一下上面没有提到的一个东西，最后一个O(sqrt(m))的循环中，逆元是没有必要每次都求的，可以预先求出来，让算法复杂度降至O(sqrt(m))。

在我的代码中，v = k^(-1) * a^(-i*m)，可以在前面先求出k^(-1)和a^(-m)，然后每次v都乘以a^(-m)，而不需要每次对k*a^(i*m)求逆元。

代码（63MS）：

 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 void exgcd(LL a, LL b, LL &x, LL &y) {
38     if(!b) x = 1, y = 0;
39     else {
40         exgcd(b, a % b, y, x);
41         y -= x * (a / b);
42     }
43 }
44 
45 LL inv(LL a, LL n) {
46     LL x, y;
47     exgcd(a, n, x, y);
48     return (x + n) % n;
49 }
50 
51 LL pow_mod(LL x, LL p, LL n) {
52     LL ret = 1;
53     while(p) {
54         if(p & 1) ret = (ret * x) % n;
55         x = (x * x) % n;
56         p >>= 1;
57     }
58     return ret;
59 }
60 
61 LL BabyStep_GiantStep(LL a, LL b, LL n) {
62     for(LL i = 0, e = 1; i <= 64; ++i) {
63         if(e == b) return i;
64         e = (e * a) % n;
65     }
66     LL k = 1, cnt = 0;
67     while(true) {
68         LL t = __gcd(a, n);
69         if(t == 1) break;
70         if(b % t != 0) return -1;
71         n /= t; b /= t; k = (k * a / t) % n;
72         ++cnt;
73     }
74     hashmap.init();
75     hashmap.insert(1, 0);
76     LL e = 1, m = LL(ceil(sqrt(n + 0.5)));
77     for(int i = 1; i < m; ++i) {
78         e = (e * a) % n;
79         hashmap.insert(e, i);
80     }
81     LL p = inv(pow_mod(a, m, n), n), v = inv(k, n);
82     for(int i = 0; i < m; ++i) {
83         LL t = hashmap.find((b * v) % n);
84         if(t != -1) return i * m + t + cnt;
85         v = (v * p) % n;
86     }
87     return -1;
88 }
89 
90 int main() {
91     LL x, z, k;
92     while(cin>>x>>z>>k) {
93         if(x == 0 && z == 0 && k == 0) break;
94         LL ans = BabyStep_GiantStep(x % z, k % z, z);
95         if(ans == -1) puts("No Solution");
96         else cout<<ans<<endl;
97     }
98 }

View Code