hdu 2815 Mod Tree (扩展BSGS算法)

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6LL k,p,n;
 7map<LL,LL>mp;
 8LL ksm(LL a,LL b,LL p)
 9{
10    LL res = 1LL;
11    while (b)
12    {
13        if (b&1) res = res * a % p;
14        b = b>>1LL;
15        a = a * a % p;
16    }
17    return res;
18}
19LL gcd( LL a,LL b){return b?gcd(b,a%b):a;}
20LL BSGS(LL a,LL b,LL p)
21{
22    a%=p;
23    b%=p;
24   // if (a==0&&b==0) return 0;
25   // if (a==0) return -1;
26    if (b==1) return 0;
27    int cnt = 0 ;
28    LL t = 1;
29    for (int g = gcd(a,p); g!=1 ; g = gcd(a,p))
30    {
31        if (b%g) return -1;
32        p/=g;
33        b/=g;
34        t=t*a/g%p;
35        cnt++;
36        if (b==t) return cnt;
37    }
38    mp.clear();
39    int m = ceil(sqrt(double(p)));
40    LL base = b ;
41    for ( LL i = 0 ; i < m ; i++)
42    {
43        mp[base] =  i;
44        base = base * a % p;
45    }
46    base = ksm(a,m,p);
47    LL ret = t ;
48    for ( int i = 1 ; i <= m+1 ; i++)
49    {
50        ret = ret * base % p;
51        if (mp.count(ret)) return i*m-mp[ret]+cnt;
52    }
53    return -1;
54}
55int main()
56{
57    #ifndef  ONLINE_JUDGE 
58    freopen("./in.txt","r",stdin);
59  #endif
60    while (~scanf("%lld%lld%lld",&k,&p,&n))
61    {
62	if (n>=p)
63	{
64	    puts("Orz,I can’t find D!");
65	    continue;
66	}
67        if (p==1) 
68	{
69	    puts("Orz,I can’t find D!");
70	    continue;
71        }
72         LL ans = BSGS(k,n,p);
73             if (ans==-1) puts("Orz,I can’t find D!");
74             else printf("%lld\n",ans);
75    }

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}