题意：裸题。。。

关于拓展BSGS的详细解释我写了一篇博文：

题解：又有一个坑，就是N>=P的时候输出无解。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 9 typedef long long LL;10 const int SIZE=40000;11 LL K,P,N;12 int bl;13 struct node{14 LL d,id;15 }bit[SIZE];16 17 bool cmp(node x,node y){18 if(x.d==y.d) return x.id
            
             >1;37 if(bit[mid].d==x) return bit[mid].id;38 if(bit[mid].d
             
              x) r=mid-1;40 }41 return -1;42 }43 44 LL exBSGS()45 {46 if(N>=P) return -1;47 LL t,m,a,b,c,g,k,x,y,add,pm,am;48 k=1;a=K;b=N;c=P;add=0;t=1;49 for(int i=0;i<=100;i++)//在约分前50 {51 if(t%c==b) return i;52 t=t*a%c;53 }54 while((g=exgcd(K,c,x,y)) != 1)55 {56 k=(k*K/g)%c;57 c/=g;//不是mod58 if(b%g) return -1;59 b/=g;add++;60 }61 m=(LL)(ceil((double)sqrt((double)c)));62 pm=1%c;bit[0].d=k%c;bit[0].id=0;63 for(int i=1;i<=m;i++)64 {65 bit[i].d=bit[i-1].d*a%c;66 bit[i].id=i;67 pm=pm*a%c;68 }69 sort(bit,bit+1+m,cmp);70 bl=0;71 for(int i=1;i<=m;i++)72 {73 if(bit[i].d!=bit[bl].d) bit[++bl]=bit[i];74 }75 exgcd(pm,c,x,y);76 am=x%c+c;//x77 t=b%c;78 for(int i=0;i<=m;i++)79 {80 x=find(t);81 if(x!=-1) return i*m+x+add;82 t=t*am%c;83 }84 return -1;85 }86 87 int main()88 {89 // freopen("a.in","r",stdin);90 // freopen("a.out","w",stdout);91 while(scanf("%I64d%I64d%I64d",&K,&P,&N)!=EOF)92 {93 LL ans=exBSGS();94 if(ans==-1) printf("Orz,I can’t find D!\n");95 else printf("%I64d\n",ans);96 }97 return 0;98 }