【题目链接】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
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);
}
}