POJ2417 Discrete Logging | A,C互质的bsgs算法

题目:

给出A,B,C

求最小的x使得A^x=B  (mod C)

---

题解:

bsgs算法的模板题

bsgs 全称:Baby-step giant-step

把这种问题的规模降低到了sqrt(n)级别

首先B的种类数不超过C种,结合鸽巢原理,所以A^x具有的周期性显然不超过C

所以一般的枚举算法可以O(C)解决这个问题

但是可以考虑把长度为C的区间分为k块,每块长度为b

显然x满足x=bi-p的形式(1<=i<=k,0<=p<b),所以A^x=B  (mod C)移项之后得到A^bi=A^p*B (mod C)

那么这个时候可以预处理出来A^p的所有值(可以用hash表维护)

//注意!hash表在插入之前要先找有没有这个值,如果有的话直接把改了就好

处理出A^b的值,枚举i,就可以得到答案

一般来说令k=b=sqrt(C)时间复杂度最优

1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<map> 5 #include<cmath> 6 #define MOD 1000007 7 #define EDGE 500000 8 typedef long long ll; 9 using namespace std; 10 ll c,a,b,ok,m,tmp,t,ans,head[MOD],ecnt; 11 struct adj 12 { 13 ll nxt,w,sum; 14 }e[EDGE]; 15 void add(ll x,ll sum) 16 { 17 ll org=x; 18 e[++ecnt].w=x; 19 x%=MOD; 20 for (int i=head[x];i;i=e[i].nxt) 21 if (e[i].w==org) 22 { 23 e[i].sum=sum; 24 return ; 25 } 26 e[ecnt].sum=sum; 27 e[ecnt].nxt=head[x]; 28 head[x]=ecnt; 29 } 30 ll qow(ll x,ll y,ll P) 31 { 32 if (y==0) return 1; 33 if (y&1) return x*qow(x*x%P,y>>1,P)%P; 34 return qow(x*x%P,y>>1,P)%P; 35 } 36 ll find(ll x) 37 { 38 ll org=x; 39 x%=MOD; 40 for (int i=head[x];i;i=e[i].nxt) 41 { 42 if (e[i].w==org) 43 return e[i].sum; 44 } 45 return -1; 46 } 47 int main() 48 { 49 while (scanf("%lld%lld%lld",&c,&a,&b)!=EOF) 50 { 51 memset(head,0,sizeof(head)); 52 ecnt=0; 53 ok=0; 54 if (a%c==0) 55 { 56 puts("no solution"); 57 continue; 58 } 59 m=ceil(sqrt(c*1.0)); 60 tmp=b%c,add(tmp,0); 61 if (b==1) 62 { 63 printf("0\n"); 64 continue; 65 } 66 for (int i=1;i<m;i++) 67 { 68 tmp=tmp*a%c; 69 add(tmp,i); 70 } 71 ll base=qow(a,m,c),tmp=1; 72 for (int i=1;i<=m;i++) 73 { 74 tmp=tmp*base%c; 75 ans=find(tmp); 76 if (ans!=-1) 77 { 78 printf("%lld\n",i*m-ans); 79 ok=1; 80 break; 81 } 82 } 83 if (!ok) 84 puts("no solution"); 85 } 86 return 0; 87 }

 

转载于:https://www.cnblogs.com/mrsheep/p/7920967.html

总结

以上是生活随笔为你收集整理的POJ2417 Discrete Logging | A,C互质的bsgs算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。