Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：
Given a prime P, 2 <= P < 231, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that BL == N (mod P)
思路：bsgs算法
详情见BSGS算法笔记
然后被map的count坑了一下？ 我想判断map中某个key是否存在，用count会TLE，find也会TLE,[]可以通过….不太懂，复杂度不都是log吗，差常数？还是有人会退化？
不过似乎[]比较安全就对了。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2017年07月23日 星期日 11时11分00秒
4File Name :2417.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34LL p,b,n;
35map<LL,LL>Hash;
36map<LL,LL>::iterator it;
37inline LL ksm(LL a,LL b,LL MOD)
38{
39 LL res = 1LL;
40 while (b)
41 {
42 if (b&1) res = (res*a)%MOD;
43 b = b >> 1;
44 a = (a*a)%MOD;
45 }
46 return res;
47}
48LL BSGS(LL a,LL b ,LL p) // a^x = b (mod p),求x
49{
50 a%=p;
51 b%=p;
52 if (!a&&!b) return 1;
53 if (!a) return -1;
54 Hash.clear();
55 LL m = ceil(sqrt(double(p)));
56 LL tmp = b;
57 for (LL j = 0 ; j <= m ; j++)
58 {
59 Hash[tmp]=j;
60 tmp = (tmp*a)%p;
61 }
62 tmp = ksm(a,m,p);
63 LL ret = 1;
64
65 for (LL i = 1 ; i <= m+1 ; i++)
66 {
67 ret = ret*tmp%p;
68 if (Hash[ret]) return i*m-Hash[ret]; //注意处理下%....虽然其实不处理也没关系...
69 }
70 return -1;
71
72}
73int main()
74{
75 #ifndef ONLINE_JUDGE
76 // freopen("./in.txt","r",stdin);
77 #endif
78 while (~scanf("%lld%lld%lld",&p,&b,&n)) // B^L = n(mod p)
79 {
80 LL ans = BSGS(b,n,p);
81 if (ans==-1) printf("no solution\n");
82 else printf("%lld\n",(ans%p+p)%p);
83 }
84
85
86 #ifndef ONLINE_JUDGE
87 fclose(stdin);
88 #endif
89 return 0;
90}