[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;
typedef
long long lld;
const
int 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);
    }
}

留下评论

您的电子邮箱地址不会被公开。