题意
求最小的x使得A^x=B(mod C)。
思路
与HDU 2815 Mod Tree、POJ 3243 Clever Y完全一致，extended BSGS的模板题。
代码
|
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; } |
