| Time Limit: 5000MS | Memory Limit: 65536K | |
| Total Submissions: 5577 | Accepted: 2494 |
Description
BL
== N (mod P)
Input
Output
Sample Input
5 2 1 5 2 2 5 2 3 5 2 4 5 3 1 5 3 2 5 3 3 5 3 4 5 4 1 5 4 2 5 4 3 5 4 4 12345701 2 1111111 1111111121 65537 1111111111
Sample Output
0 1 3 2 0 3 1 2 0 no solution no solution 1 9584351 462803587
Hint
B(P-1)
== 1 (mod P)
B(-m)
== B(P-1-m)
(mod P) .
Source
#include<cmath> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; struct Thash{ static const int MOD=233333; static const int MAXN=1e6+5; int tot,head[MOD+100],next[MAXN],h[MAXN],val[MAXN]; inline void clear(){tot=0;memset(head,0,sizeof head);} inline void insert(int H,int VAL){ for(int i=head[H%MOD];i;i=next[i]) if(h[i]==H){val[i]=VAL;return ;} h[++tot]=H;val[tot]=VAL;next[tot]=head[H%MOD];head[H%MOD]=tot; } inline int get(int H){ for(int i=head[H%MOD];i;i=next[i]) if(h[i]==H) return val[i]; return 0; } }M; inline ll fpow(ll a,ll p,ll mod){ int res=1; for(;p;p>>=1,a=a*a%mod) if(p&1) res=res*a%mod; return res; } int BSGS(ll A,ll B,ll mod){ A%=mod; if(!A){ if(!B) return 1; return -1; } ll m=sqrt(mod)+1,ni=fpow(A,mod-m-1,mod); ll t=1,y=1; M.clear(); M.insert(1,m+1); for(int i=1;i<m;i++){ t=t*A%mod; if(!M.get(t)) M.insert(t,i); } for(int i=0;i<m;i++){ int u=M.get(B*y%mod); if(u){ if(u==m+1) u=0; return i*m+u; } y=y*ni%mod; } return -1; } int main(){ int a,b,c,ans(-1); while(scanf("%d%d%d",&c,&a,&b)==3){ ans=BSGS(a,b,c); if(~ans) printf("%d\n",ans); else puts("no solution"); } return 0; }
POJ2417 Discrete Logging【BSGS】
原文：http://www.cnblogs.com/shenben/p/6516478.html