[HDOJ2815 Mod Tree]【扩展Baby step Giant step】

【题目链接】http://acm.hdu.edu.cn/showproblem.php?pid=2815

【题目大意】给定a,p,c让你求满足 a^x = c (mod p)的最小非负整数解

【算法分析】

详细的讲解：

【扩展Baby Step Giant Step解决离散对数问题】http://hi.baidu.com/aekdycoin/blog/item/b317ca18bb24334942a9ad55.html

By AekdyCoin

【Result】

33876852011-01-11 07:23:30Accepted2815421MS928K2498 BG++edward_mj

【吐槽】

倒3的时间。

分析一下原因：

1、cin。其实这个应该没有任何影响。

2、memset了hash的数组。

3、exgcd用了lld。

。。。这种速度绝对不能作为模板了= =

【CODE】

#include #include #include #include #include using namespace std;
typedeflong long lld;
constint N=100003;

struct Baby_step_Giant_step{
       struct edge{int key,times;edge*next;}g[N],*ls[N];
       int e;
      
       void add(int x,int times){
            int hash=x%N;
            for(edge*t=ls[hash];t;t=t->next)
              if(t->key==x)return;
            g[++e].key=x; g[e].times=times; g[e].next=ls[hash]; ls[hash]=&g[e];
       }
      
       int In(int x){
           int hash=x%N;
           for(edge*t=ls[hash];t;t=t->next)
             if(t->key==x)return t->times;
           return–1;
       }
      
       int Power_mod(int a,int b,int Mod){
           lld t=a,res=1;
           while(b){
                 if(b&1) res=res*t%Mod;
                 t=t*t%Mod;
                 b>>=1;
           }
           return(int)(res);
       }
      
       lld exgcd(int a,int b,lld&x,lld&y){
           if(b==0){
             x=1;
             y=0;
             return a;
           }
           lld g=exgcd(b,a%b,x,y);
           lld tx=x,ty=y;
           x=ty;
           y=tx–a/b*ty;
           return g;
       }
      
       int  solve(int a,int c,int p){
            if(c>=p)return–1;
            int i,j;
            int x=1;
            int t=1;
            int s=(int)ceil(sqrt((double)p));
            int res;
            int cnt=0;
            lld tx,ty,g;
            for(i=0;i<=50;i++)if(Power_mod(a,i,p)==c)return i;
           
            while((g=exgcd(a,p,tx,ty))!=1){
                  if(c%g)return–1;
                  c/=g;
                  p/=g;
                  x=(lld)(a)/g*x%p;
                  cnt++;
            }
           
            e=0;
            memset(ls,0,sizeof(ls));
            for(i=0;i<s;i++) add(Power_mod(a,i,p),i);
           
            for(int step=Power_mod(a,s,p),i=cnt;i<p;i+=s,x=(lld)(x)*step%p){
                g=exgcd(x,p,tx,ty);
                tx=tx*c%p;
                if(tx<0) tx+=p;
                res=In((int)tx);
                if(res==-1)continue;
                return res+i;
            }
            return–1;
       }     
}Number_Theory;

intmain(){
    int a,p,c;
    while(cin>> a>> p>> c){
      int ans=Number_Theory.solve(a,c,p);
      if(ans==-1) puts("Orz,I can’t find D!");
              else printf("%dn",ans);
    }
}