BSGS
即baby(boy) step giant(girl) step算法，用于处理\(a^x\equiv b(mod\ p)\)，给\(a,b,p(a,p互质)\)求所有的 \(x\) 的问题中
本质上有一点点像二分搜索的意味在里面
算法流程
有\(a^x \equiv b(mod\ p)\)
令\(x = A \lceil \sqrt p \rceil - B\)，其中\(0\leq A,B \leq \lceil\sqrt p \rceil\)
\(\Rightarrow a^{A\lceil \sqrt p \rceil - B} \equiv b(mod p)\)
\(\Rightarrow a^{A\lceil \sqrt p \rceil} \equiv b \times a^B(mod p)\)
我们可以把所有的\(b\times a^i,i\in [1,\lceil \sqrt p\rceil]\) 存在一个映射数据结构（hash/map/unordered_map）上
枚举A(\(1\rightarrow n\))，在映射数据结构上查找是否含有\(a^{A\lceil\sqrt p \rceil}\)，
时间复杂度
显然地，复杂度为\(\Theta(\sqrt p)\)，(因为\(A,B\leq \sqrt p\) )
如果使用map/unordered_map则为\(\Theta(log_p \sqrt p )\)
警戒点
- \(\sqrt p\)一定要上取整
- \(b\times a^i\) ,i从0->n!
- \(a^i\) ,i从1->n!
代码
typedef long long ll;
map<ll,ll> Map;
ll BSGS(ll a,ll b,ll p){
Map.clear();
ll t = ceil(sqrt(p));//必须加上ceil
ll k = 1;
Map[b%p] = 0;
for(ll i = 1; i <= t; ++i)Map[(k = k * a % p) * b % p] = i;//计算b*a^i
a = 1;
for(ll i = 1; i <= t; ++i){
a = a * k % p;
if(Map.count(a))//在映射数组中找a^i
return i*t-Map[a];
}
return -1;
}
int main(){
ll p,b,n,ans;
while(~scanf("%lld%lld%lld",&p,&b,&n))
if((ans = BSGS(b,n,p)) != -1)printf("%lld\n",ans);
else puts("no solution");
return 0;
}
exBSGS
exBSGS \(a^x\equiv b(mod\ p)\)，给\(a,b,p\)\((b,p\)不互质\()\)求所有的 \(x\) 的问题中
此时\(a\times a^{x-1} \equiv b(mod\ p)\)，令\(d = gcd(a,p)\)
左右同除\(d\)
\(\therefore \frac{a}{d}\times a^{x-1} \equiv \frac{b}{d}(mod\ gcd(a,p))\)
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll> Map;
ll BSGS(ll a,ll b,ll p){
Map.clear();
ll t = ceil(sqrt(p));
ll k = 1;
Map[b%p] = 0;
for(ll i = 1; i <= t; ++i)Map[(k = k * a % p) * b % p] = i;
a = 1;
for(ll i = 1; i <= t; ++i){
a = a * k % p;
if(Map.count(a))
return i*t-Map[a];
}
return -1;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){x = 1;y = 0;return a;}
ll d = exgcd(b,a%b,x,y);
ll t = x;
x = y;
y = t - (a/b) * y;
return d;
}
ll inv(ll a,ll b){
ll x,y;
exgcd(a,b,x,y);
return (x % b + b) % b;
}
ll ksm(ll x,ll k,ll p){
ll res = 0,a = k % p;
while(k){
if(k&1)res = res * a % p;
a = a * a % p;
k >>= 1;
}
}
ll gcd(ll x,ll y){return y ? gcd(y,x%y) : x;}
ll x = 1;
ll exBSGS(ll a,ll b,ll p){
ll d = gcd(a,p);
if(b == x)return 0;
if(d == 1){
return BSGS(a,b*inv(x,p) % p,p);
}
if(b % d != 0)return -1;
else{
x = a/d * x % (p/d);
ll res = exBSGS(a,b/d,p/d);
if(res == -1)return -1;
if(res == -2)return -2;
return res + 1;
}
}
ll a,p,b;
int main(){
while(~scanf("%lld%lld%lld",&a,&p,&b)){
x = 1;
if(a == 0 && b == 0 && p == 0)break;
a%=p;b%=p;
if(b==1||p==1){
puts("0");continue;
}
ll res = exBSGS(a%p,b%p,p);
if(res == -1)puts("No Solution");
else printf("%lld\n",res);
}
}