一道裸的BSGS題目（叫baby step, giant step）

從愛醬的blog里學來的，是一個很神的根號算法。

如果我們有hash的工具的話，就是O(sqrt(p))的，這里又用了一個map所以是O(sqrt(p) * log(sqrt(p)))

?

1 /************************************************************** 2 Problem: 3239 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:280 ms 7 Memory:2932 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cmath> 12 #include <map> 13 14 using namespace std; 15 typedef long long ll; 16 17 ll p, y, z, B; 18 map <ll, int> mp; 19 20 ll pow(ll a, ll x) { 21 a %= p; 22 ll res = 1, base = a; 23 while (x) { 24 if (x & 1) (res *= base) %= p; 25 (base *= base) %= p; 26 x >>= 1; 27 } 28 return res; 29 } 30 31 int main() { 32 ll i, now, base, tmp; 33 while (scanf("%lld%lld%lld", &p, &y, &z) != EOF) { 34 mp.clear(); 35 y %= p; 36 if (!y) { 37 if (!z) puts("1"); 38 else puts("no solution"); 39 goto end_of_work; 40 } 41 B = (int) ceil(sqrt(p)), now = 1; 42 mp[1] = B + 1; 43 for (i = 1; i < B; ++i) { 44 (now *= y) %= p; 45 if (!mp[now]) mp[now] = i; 46 } 47 now = 1, base = pow(y, p - B - 1); 48 for (i = 0; i < B; ++i) { 49 tmp = mp[z * now % p]; 50 if (tmp) { 51 if (tmp == B + 1) tmp = 0; 52 printf("%lld\n", i * B + tmp); 53 goto end_of_work; 54 } 55 (now *= base) %= p; 56 } 57 puts("no solution"); 58 end_of_work:; 59 } 60 return 0; 61 } View Code

(p.s. bz上開了O2，所以還不是很慢恩！)

轉載于:https://www.cnblogs.com/rausen/p/4263251.html

總結

以上是生活随笔為你收集整理的BZOJ3239 Discrete Logging的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。