题意
求解最小的x使得A^x=B(mod C)成立，C不保证是素数。
思路
C不保证素数的BSGS，这时使用扩展BSGS解决，扩展BSGS的实质是在BSGS之前利用这个定理：
Ad=Bd(mod C) <=> A=B(mod C/gcd(C,d))
将问题转化为一般BSGS能够解决的形式，再使用一般BSGS解决。
代码
POJ 2417 Discrete Logging这个问题中也使用了如下exBSGS的代码。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; #pragma mark - Extended Baby-Step-Gaint-Step Algorithm (exBSGS) struct Hashtable{//Mod Based Hash Table static const int HASHMOD = 3894229;//A Prime long long top, hash[HASHMOD+100], value[HASHMOD+100], stk[1 << 16]; int locate(long long &x){ int h = x % HASHMOD; while(hash[h] != -1 && hash[h] != x){ h++; } return h; } void insert(long long key,long long val){ int h = locate(key); if(hash[h] == -1){ hash[h] = key; value[h] = val; stk[++top] = h; } } long long find(long long &key){ int h = locate(key); return (hash[h] == key)?value[h]:-1; } void clear(){ while(top){ hash[stk[top--]] = -1; } } Hashtable(){ top = 0; memset(hash, -1, sizeof(hash)); } } hashtab; struct Triple{ long long x,y,z; Triple(long long _x, long long _y, long long _z){ x = _x; y = _y; z = _z; } Triple(){ x = y = z = 0; } }; Triple exgcd(long long a,long long b){ //for inv use(A/B % C):let a = B,b = C,return.x = inv,return.z = gcd //for solve use:return.x = specx,return.y = specy,returnz = gcd if (b == 0) { return Triple(1,0,a); } Triple last = exgcd(b, a%b); return Triple(last.y, last.x - a / b * last.y, last.z); } long long exBSGS(long long A,long long B,long long C){ //A^x=B(mod C) //Ensure B is legal B %= C; if (B < 0) { B += C; } //Procceed A,B,C to normal BSGS if C is not prime long long tmp = 1, cnt = 0, D = 1; for (int i = 0; i < 64; i++) { if (tmp == B) { return i; } tmp = tmp * A % C; } for (Triple res; (res = exgcd(A, C)).z != 1; cnt++) { if (B % res.z) { return -1; } B /= res.z; C /= res.z; D = D * A / res.z % C; } //Normal BSGS long long sqrtn = (long long)(ceil(sqrt(C))); hashtab.clear(); long long base = 1; for (int i = 0; i < sqrtn; i++) { hashtab.insert(base, i); base = base * A % C; } long long j = -1,i = 0; for (; i < sqrtn; i++) { Triple res = exgcd(D, C); long long c = C / res.z; res.x = (res.x * B/res.z % c + c) % c; j = hashtab.find(res.x); if (j != -1) { return i * sqrtn + j + cnt; } D = D * base % C; } return -1; } #pragma mark - int main(){ long long a,b,c; while (scanf(" %lld %lld %lld",&a,&c,&b) != EOF) { if (a == 0 && b == 0 && c == 0) { break; } long long ret = exBSGS(a, b, c); if (ret == -1) { puts("No Solution"); }else{ printf("%lld\n",ret); } } return 0; } |
