题意
题目翻译好之后实际上是求解最小的x使得A^x=B(mod C)成立，C不保证是素数。
思路
典型的Extended BSGS模板题。
需要注意的是，内存空间比较紧张，HASH空间不宜开得太大，需要牺牲一些时间换空间。
代码
|
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 |
#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 = 1200611;//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) { long long ret = exBSGS(a, b, c); if (b >= c || ret == -1) { puts("Orz,I can’t find D!"); }else{ printf("%lld\n",ret); } } return 0; } |
October 22, 2015
[…] 与HDU 2815 Mod Tree、POJ 3243 Clever Y完全一致，extended BSGS的模板题。 […]