一道裸的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 ", 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 }
(p.s. bz上开了O2，所以还不是很慢恩！)