北上广深 拔山盖世……
还是叫大步小步吧……
· 算法概述
BSGS算法 又叫 大步小步算法。用于求解关于 $x$ 的方程 $A^x\equiv B\pmod{P}$ ($A$,$B$,$P$ 为已知),其中 $P$ 是质数 。
当然方程有可能无解。
· 算法证明
首先证明“如果原方程有解,则在 $x\in[0,P-1)$ 范围内有解”:
根据费马小定理:$A^{P-1}\equiv 1\pmod{P}$ ;
那么可以得到:$A^{x+k(P-1)}\equiv A^x\pmod{P}$ ($k$ 为整数);
即 $A^x\equiv A^{x\bmod (P-1)}\pmod P$ ;得证。
令 $x=pm-q$ ($m$ 为一个常数且 $q<m$),那么原方程就变为 $A^{pm-q}\equiv B\pmod{P}$ ;
两边同乘 $A^q$ :$A^{pm}\equiv BA^q\pmod{P}$ ;
先枚举 $q\in[0,m)$ 并算出对应的 $(A^q \bmod P)$ 存入集合;
再枚举 $p$ 直到 $pm+q>P-1$ ,计算 $(A^{pm}\bmod P)$ 并在集合里查找,如果找到了,就找到了一个解;
时间复杂度 $O(\max(m,\lceil\frac{P}{m}\rceil))$ 。
所以当 $m=\lceil\sqrt{P}\rceil$ 时,BSGS的时间复杂度达到最小 $O(\sqrt P)$ 。
多组数据,每次给出 $A,B,P$ ,求关于 $x$ 的方程的 $A^x\equiv B\pmod{P}$ 的最小非负整数解。如果无解输出 no solution
。
Tab. $P< 2^{31},2\leq A<P,1\leq B<P$
- 解析
用 map 会 TLE,手打链表 hash 。
然后特判一下 $B=1$ 的时候直接 $x=0$ 。
- 源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
| #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<map> using namespace std; typedef long long ll; const ll MOD=1389001; ll B,N,P; ll adj[MOD],lst[2*MOD][2],nxt[2*MOD],cnt; ll QPow(ll a,ll b){ ll res=1; while(b){ if(b&1ll) res=res*a%P; a=a*a%P; b>>=1ll; } return res%P; } int SearchHash(ll num){ ll fnum=num%MOD; for(int i=adj[fnum];i!=-1;i=nxt[i]) if(lst[i][0]==num) return i; return -1; } void Insert(ll num,ll val){ ll fnum=num%MOD; lst[++cnt][0]=num; lst[cnt][1]=val; nxt[cnt]=adj[fnum]; adj[fnum]=cnt; } int main(){ while(~scanf("%lld%lld%lld",&P,&B,&N)){ if(N==1){printf("%d\n",0);continue;} memset(adj,-1,sizeof adj);cnt=0; ll M=(ll)ceil(sqrt(P)); for(ll q=0,num=N;q<M;q++){ int X=SearchHash(num); if(X==-1) Insert(num,q); else lst[X][1]=q; num=num*B%P; } ll BM=QPow(B,M); bool abl=false; for(ll p=1,num=1;p<=M;p++){ num=num*BM%P; int X=SearchHash(num); if(X!=-1){ abl=true; printf("%lld\n",p*M-lst[X][1]); break; } } if(!abl) printf("no solution\n"); } return 0; }
|
The End
Thanks for reading!
Email: lucky_glass@foxmail.com ,欢迎提问~