北上广深 拔山盖世……
还是叫大步小步吧……
· 算法概述
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 ，欢迎提问~