本文共 2541 字，大约阅读时间需要 8 分钟。
数论的题目，这题是可以直接暴力搜出来的，不过正解应该是Baby-Step-Giant-Step（以下简称BSGS）。
下面的解释只适用于底数与模互质，其他情况是不能解出正确答案的。正确的BSGS解法在之后两篇中有介绍！
其实BSGS的原理十分简单，就是将被搜索的数分解成i * (sqrt(m) + 1) + j（m是等式中的模）的形式，先求出1~(srqt(m) + 1)的所有mod m的余数，这个步骤因为跨越的区间小，所以这叫Baby-Step。然后就是Giant-Step，每次跳跃。如果借助hash函数，在exgcd求逆模以后，就可以直接O(1)查找是否有满足要求的Baby-Step。如果是用map映射，那么就是O(logn)的复杂度查找。于是整体的复杂度就是O(n)或者O(nlongn)，其中n是sqrt(m) + 1。
下面是原创代码，giantStep函数可以解p^x mod m = rest形式的方程的：
1 /* 2 * Author: Lyon 3 * Problem: hdu 1395 4 * Method: Baby-Step Giant-Step 5 */ 6 7 #include 8 #include 9 #include 10 #include 11 #include 12 13 using namespace std; 14 map index; 15 16 bool babyStep(int p, int mod, int &r, int rest){ 17 int cur = 1; 18 19 r = (int) sqrt((double) mod) + 1; 20 index.clear(); 21 for (int i = 1; i <= r; i++){ 22 cur *= p; 23 cur %= mod; 24 if (cur == rest){ 25 r = i; 26 return true; 27 } 28 index[cur] = i; 29 } 30 31 return false; 32 } 33 34 void exgcd(int a, int b, int &x, int &y, int &d, int rest){ 35 if (b){ 36 exgcd(b, a % b, y, x, d, rest); 37 y -= x * (a / b); 38 } 39 else{ 40 d = a; 41 x = rest; 42 y = 0; 43 } 44 } 45 46 int gcd(int a, int b){ 47 return b ? gcd(b, a % b) : a; 48 } 49 50 int multiMod(int a, int b, int m){ 51 int ret = 0; 52 53 while (b){ 54 if (b & 1) ret += a, ret %= m; 55 a <<= 1; 56 a %= m; 57 b >>= 1; 58 } 59 60 return ret; 61 } 62 63 int powMod(int p, int n, int m){ 64 int ret = 1; 65 66 p %= m; 67 while (n){ 68 if (n & 1){ 69 ret = multiMod(ret, p, m); 70 } 71 p = multiMod(p, p, m); 72 n >>= 1; 73 } 74 75 return ret; 76 } 77 78 int giantStep(int p, int mod, int rest){ // calculate p^x % mod = rest 79 int r, x, y, d; 80 81 if (rest % gcd(p, mod)) return -1; 82 if (babyStep(p, mod, r, rest)){ 83 return r; 84 } 85 else{ 86 int tmp = powMod(p, r, mod); 87 int ep = tmp; 88 89 for (int i = 1; i <= r; i++){ 90 exgcd(ep, mod, x, y, d, rest); 91 while (x >= 0) x -= mod; 92 while (x < 0) x += mod; 93 if (index.count(x)){ 94 return i * r + index[x]; 95 } 96 ep = multiMod(ep, tmp, mod); 97 } 98 } 99 100 return -1;101 }102 103 int main(){104 int n;105 106 while (~scanf("%d", &n)){107 if (n == 1){108 puts("2^? mod 1 = 1");109 continue;110 }111 112 int ans = giantStep(2, n, 1);113 114 if (~ans){115 printf("2^%d mod %d = 1\n", ans, n);116 }117 else printf("2^? mod %d = 1\n", n);118 }119 120 return 0;121 }
——written by Lyon
转载于:https://www.cnblogs.com/LyonLys/archive/2012/09/17/hdu_1395_Lyon.html
View Code