hdu 2815 Mod Tree (扩展BSGS算法)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :Mon 24 Jul 2017 09:43:41 PM CST
  4File Name :2815.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 k,p,n;
 35map<LL,LL>mp;
 36LL ksm(LL a,LL b,LL p)
 37{
 38    LL res = 1LL;
 39    while (b)
 40    {
 41        if (b&1) res = res * a % p;
 42        b = b>>1LL;
 43        a = a * a % p;
 44    }
 45    return res;
 46}
 47LL gcd( LL a,LL b){return b?gcd(b,a%b):a;}
 48LL BSGS(LL a,LL b,LL p)
 49{
 50    a%=p;
 51    b%=p;
 52   // if (a==0&&b==0) return 0;
 53   // if (a==0) return -1;
 54    if (b==1) return 0;
 55    int cnt = 0 ;
 56    LL t = 1;
 57    for (int g = gcd(a,p); g!=1 ; g = gcd(a,p))
 58    {
 59        if (b%g) return -1;
 60        p/=g;
 61        b/=g;
 62        t=t*a/g%p;
 63        cnt++;
 64        if (b==t) return cnt;
 65    }
 66    mp.clear();
 67    int m = ceil(sqrt(double(p)));
 68    LL base = b ;
 69    for ( LL i = 0 ; i < m ; i++)
 70    {
 71        mp[base] =  i;
 72        base = base * a % p;
 73    }
 74    base = ksm(a,m,p);
 75    LL ret = t ;
 76    for ( int i = 1 ; i <= m+1 ; i++)
 77    {
 78        ret = ret * base % p;
 79        if (mp.count(ret)) return i*m-mp[ret]+cnt;
 80    }
 81    return -1;
 82}
 83int main()
 84{
 85    #ifndef  ONLINE_JUDGE 
 86    freopen("./in.txt","r",stdin);
 87  #endif
 88    while (~scanf("%lld%lld%lld",&k,&p,&n))
 89    {
 90	if (n>=p)
 91	{
 92	    puts("Orz,I can’t find D!");
 93	    continue;
 94	}
 95        if (p==1) 
 96	{
 97	    puts("Orz,I can’t find D!");
 98	    continue;
 99        }
100         LL ans = BSGS(k,n,p);
101             if (ans==-1) puts("Orz,I can’t find D!");
102             else printf("%lld\n",ans);
103    }
104
105  #ifndef ONLINE_JUDGE  
106  fclose(stdin);
107  #endif
108    return 0;
109}