Discrete Logging POJ - 2417（BSGS）

Discrete Logging

 POJ - 2417 

题意：给P，B，N，求最小的L使得 B^L≡N (mod P)，其中P是素数。

Baby Step Giant Step

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <cmath> 5 #define ll long long 6 using namespace std; 7 const int mod=99991; 8 ll head[mod],nex[mod]; 9 ll cnt; 10 ll hs[mod],id[mod]; 11 void init(){ 12 memset(head,-1,sizeof(head)); 13 cnt=0; 14 } 15 void insert_(ll x,ll i){ 16 hs[cnt]=x;id[cnt]=i; 17 ll u=x%mod; 18 nex[cnt]=head[u]; 19 head[u]=cnt++; 20 } 21 ll find_(ll x){ 22 int u=x%mod; 23 for(int i=head[u];~i;i=nex[i]){ 24 if(hs[i]==x) return id[i]; 25 } 26 return -1; 27 } 28 //求解A^x≡B(mod C),返回x，若无解返回-1 29 ll bsgs(ll a,ll b,ll c){ 30 if(b==1) return 0; 31 ll m=ceil(sqrt(c*1.0)); 32 ll q=1; 33 for(ll i=0;i<=m;i++){ 34 if(i==0) insert_(b%c,i); 35 else{ 36 q=q*a%c; 37 insert_(q*b%c,i); 38 } 39 } 40 ll temp=1; 41 for(ll i=1;i<=m;i++){ 42 temp=temp*q%c; 43 ll j=find_(temp); 44 if(j!=-1) return i*m-j; 45 } 46 return -1; 47 } 48 ll a,b,c; 49 int main(){ 50 while(scanf("%lld%lld%lld",&c,&a,&b)!=EOF){ 51 init(); 52 ll ans=bsgs(a,b,c); 53 if(ans!=-1) printf("%lld\n",ans); 54 else puts("no solution"); 55 } 56 } View Code

 

转载于:https://www.cnblogs.com/yijiull/p/7385093.html

总结

以上是生活随笔为你收集整理的Discrete Logging POJ - 2417（BSGS）的全部内容，希望文章能够帮你解决所遇到的问题。

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