【hdu2815-Mod Tree】高次同余方程-拓展BadyStepGaintStep

http://acm.hdu.edu.cn/showproblem.php?pid=2815

题意：裸题。。。

关于拓展BSGS的详细解释我写了一篇博文：http://www.cnblogs.com/KonjakJuruo/p/5178600.html

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

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int SIZE=;

 LL K,P,N;

 int bl;

 struct node{

     LL d,id;

 }bit[SIZE];

 bool cmp(node x,node y){

     if(x.d==y.d) return x.id<y.id;

     return x.d<y.d;

 }

 LL exgcd(LL a,LL b,LL &x,LL &y)

 {

     if(b==) {x=,y=;return a;}

     LL tx,ty;

     LL d=exgcd(b,a%b,tx,ty);

     x=ty;y=tx-(a/b)*ty;

     return d;

 }

 LL find(LL x)

 {

     int l=,r=bl;

     while(l<=r)

     {

         int mid=(l+r)>>;

         if(bit[mid].d==x) return bit[mid].id;

         if(bit[mid].d<x) l=mid+;

         if(bit[mid].d>x) r=mid-;

     }

     return -;

 }

 LL exBSGS()

 {

     if(N>=P) return -;

     LL t,m,a,b,c,g,k,x,y,add,pm,am;

     k=;a=K;b=N;c=P;add=;t=;

     for(int i=;i<=;i++)//在约分前

     {

         if(t%c==b) return i;

         t=t*a%c;

     }

     while((g=exgcd(K,c,x,y)) != )

     {

         k=(k*K/g)%c;

         c/=g;//不是mod

         if(b%g) return -;

         b/=g;add++;

     }

     m=(LL)(ceil((double)sqrt((double)c)));

     pm=%c;bit[].d=k%c;bit[].id=;

     for(int i=;i<=m;i++)

     {

         bit[i].d=bit[i-].d*a%c;

         bit[i].id=i;

         pm=pm*a%c;

     }

     sort(bit,bit++m,cmp);

     bl=;

     for(int i=;i<=m;i++)

     {

         if(bit[i].d!=bit[bl].d) bit[++bl]=bit[i];

     }

     exgcd(pm,c,x,y);

     am=x%c+c;//x

     t=b%c;

     for(int i=;i<=m;i++)

     {

         x=find(t);

         if(x!=-) return i*m+x+add;

         t=t*am%c;

     }

     return -;

 }

 int main()

 {

     // freopen("a.in","r",stdin);

     // freopen("a.out","w",stdout);

     while(scanf("%I64d%I64d%I64d",&K,&P,&N)!=EOF)

     {

         LL ans=exBSGS();

         if(ans==-) printf("Orz,I can’t find D!\n");

         else printf("%I64d\n",ans);

     }

     return ;

 }

hdu2815