hdu 2815 Mod Tree

http://acm.hdu.edu.cn/showproblem.php?pid=2815

　　题意很简单，转换过来，就是要求满足K^x mod P = N的最小X。

　　这是专业版的Baby-Step Giant-Step，相对之前那个hdu 1395的BSGS的用途广泛的多。这里的算法可以解决当底数与模非互质的时候，满足条件的X的最小值。

　　BSGS粗略的说，就是像我前两篇随笔的解释一样。不过，实际解决问题的时候，如果底数与模不是互质，那么exgcd求AX mod B = C中，X的解并不正确。因此，在该过程前，要将式子中的A与B互质，从而解出唯一解！使得两者互质的过程如下：

while((tmp=gcd(A，B))!=1){

　　if(B％tmp)return -1; // 无解!

　　++d;

　　B/=tmp;

　　C/=tmp;

　　D=D*A/tmp％C;

}

　　这个消因子的步骤十分关键，详细的解释点击链接，里面有这个过程的证明，我就不一一叙述了。

　　这次的代码中间有部分思路不太清晰，所以写得有点乱：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <map>
  5 #include <algorithm>
  6 
  7 using namespace std;
  8 typedef __int64 ll;
  9 
 10 //map<int, int> EP;
 11 
 12 const int maxn = 500007;
 13 int hash[maxn], EP[maxn];
 14 
 15 bool insert(int x, int k){
 16     int p = (x << 6) % maxn;
 17 
 18     if (p < 0) p += maxn;
 19     while (hash[p] != x && ~EP[p]) p = (p + 1) % maxn;
 20 
 21     if (hash[p] == x && ~EP[p]) return false;
 22 
 23     hash[p] = x;
 24     EP[p] = k;
 25 
 26     return true;
 27 }
 28 
 29 int find(int x){
 30     int p = (x << 6) % maxn;
 31 
 32     if (p < 0) p += maxn;
 33     while (hash[p] != x && ~EP[p]) p = (p + 1) % maxn;
 34 
 35     return EP[p];
 36 }
 37 
 38 int gcd(int a, int b){
 39     return b ? gcd(b, a % b) : a;
 40 }
 41 
 42 void exgcd(int a, int b, ll &x, ll &y){
 43     if (b){
 44         exgcd(b, a % b, y, x);
 45         y -= (a / b) * x;
 46     }
 47     else{
 48         x = 1;
 49         y = 0;
 50     }
 51 }
 52 
 53 int multiMod(int a, int b, int m){
 54     int ret = 0;
 55 
 56     while (b){
 57         if (b & 1) ret += a, ret %= m;
 58         a <<= 1;
 59         a %= m;
 60         b >>= 1;
 61     }
 62 
 63     return ret;
 64 }
 65 
 66 int powMod(int p, int n, int m){
 67     int ret = 1;
 68 
 69     while (n){
 70         if (n & 1) ret = multiMod(ret, p, m);
 71         p = multiMod(p, p, m);
 72         n >>= 1;
 73     }
 74 
 75     return ret;
 76 }
 77 
 78 int babyStep(int &p, int &m, int &rest, int &cnt, int &mark){
 79     int t, cur = 1 % m;
 80     int tp = p, tm = m, trest = rest;
 81 
 82     cnt = 0;
 83 //    EP.clear();
 84     memset(EP, -1, sizeof(EP));
 85     while ((t = gcd(p, m)) != 1){
 86         if (cur == rest) return 0;
 87         if (rest % t) return -1;
 88         cnt++;
 89         m /= t;
 90         rest /= t;
 91         cur = multiMod(cur, p / t, m);
 92     }
 93     mark = cur;
 94     cur = 1 % tm;
 95     for (int i = 0; i <= cnt; i++){
 96         if (cur == trest){
 97             cnt = i;
 98             return 0;
 99         }
100         cur = multiMod(cur, tp, tm);
101     }
102     cur = 1 % m;
103 
104     int r = (int) ceil(sqrt((double) m));
105 
106     for (int i = 0; i <= r; i++){
107 //        if (EP.count(cur)) break;
108 //        EP[cur] = i;
109         if (!insert(cur, i)) break;
110         cur = multiMod(cur, p, m);
111     }
112 
113     return r;
114 }
115 
116 int giantStep(int p, int m, int rest){
117     int tmp, cnt;
118 
119     if (rest >= m) return -1;
120 
121     int r = babyStep(p, m, rest, cnt, tmp);
122 
123     if (r == -1) return -1;
124 
125     int ep = powMod(p, r, m);
126 
127     if (!r)    return cnt;
128     for (int i = 0; i < r; i++){
129         ll x, y;
130 
131         exgcd(tmp, m, x, y);
132         x %= m;
133         x *= rest;
134         x %= m;
135         if (x < 0) x += m;
136 //        if (EP.count((int)x)){
137 //            return EP[(int)x] + i * r + cnt;
138 //        }
139         int f = find((int)x);
140 
141         if (~f) return f + i * r + cnt;
142         tmp = multiMod(tmp, ep, m);
143     }
144 
145     return -1;
146 }
147 
148 int main(){
149     int k, p, n;
150 
151     while (~scanf("%d%d%d", &k, &p, &n)){
152         int ans = giantStep(k, p, n);
153 
154         if (~ans) printf("%d\n", ans);
155         else puts("Orz,I can’t find D!");
156     }
157 
158     return 0;
159 }

——written by Lyon