$\text{BSGS}$ 用于解决形如
\[a^k\equiv b\pmod p,\gcd(a,p)=1\]的求指数(最小)的问题.
方法十分简单:
设
\[m=\lceil\sqrt{p}\rceil\]则
\[k=xm-y\]移项
\[a^{xm}\equiv b\cdot a^y \pmod p\]首先枚举 $y$ ,将 $s=b\cdot a^y(mod\ p)$ 的结果用 $map$ 存下来.
由于在 $x$ 相等的情况下, $y$ 越大越好,所以从小到大枚举 $y$ 时直接用 $i$ 更新 $mp[s]$ .
然后再枚举 $x$ 即可.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <map>
#define pr(p) printf("%d\n",p)
const int oo=2139063143;
const int N=1010000;
using namespace std;
typedef long long LL;
typedef double db;
inline void sc (int &x)
{
x=0; static int p; p=1; static char c; c=getchar();
while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
x*=p;
}
int p,a,b;
int ksm (int a,int b)
{
int ans=1;
while (b)
{
if (b&1) ans=1LL*ans*a%p;
a=1LL*a*a%p;
b>>=1;
}
return ans;
}
map <int,int> mp;
int BSGS ()
{
int m=sqrt (p)+1;
int s=b;
for (int i=0; i< m; i++)
mp[s]=i,s=1LL*s*a%p;
int g=ksm (a,m);
s=1;
for (int i=1; i<=m; i++)
{
s=1LL*s*g%p;
if (mp.find (s)!=mp.end ()) return i*m-mp[s];
}
return -1;
}
int main()
{
//freopen (".in","r",stdin);
//freopen (".out","w",stdout);
sc(p),sc(a),sc(b);
int ans=BSGS ();
if (ans!=-1) pr(BSGS ());
else puts("no solution");
return 0;
}
当 $a,p$ 不互质时,不能直接用普通的 $\text{BSGS}$ ,于是需要对原式进行一些变化,使得 $a^{‘}$ 与 $p^{‘}$ 互质.
首先设
\[d=\gcd(a,p)\]令原式变形为
\[a^{k-1}\cdot \frac{a}{d}\equiv \frac{b}{d} \pmod {\frac{p}{d}}\]设
\[s=\frac{a}{d},b^{'}=\frac{b}{d},p^{'}=\frac{p}{d}\]则原式为
\[s\cdot a^{k-1}\equiv b^{'} \pmod {p^{'}}\]此时 $a$ 与 $p^{‘}$ 可能仍不互质,于是继续分解,直到两者互质为止.
\[\frac{a^{cnt}}{\prod d_i}\cdot a^{k-cnt}\equiv \frac{b}{\prod_{i}d_i} \pmod {\frac{p}{\prod_{i}d_i}}\]最后直接进行普通 $\text{BSGS}$ 即可.
有一些特殊情况:
$\text{1.}$ 分解前,若 $b==1$ ,则可直接返回 $k=0$ .
$\text{2.}$ 分解时,若 $d\not | b$ ,则无解,返回 $k=-1$ .
$\text{3.}$ 分解时,若 $a$ 前的系数恰好等于 $b$ , 直接返回当前的 $cnt$ .
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <map>
#define pr(p) printf("%d\n",p)
const int oo=2139063143;
const int N=1010000;
using namespace std;
typedef long long LL;
typedef double db;
inline void sc (int &x)
{
x=0; static int p; p=1; static char c; c=getchar();
while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
x*=p;
}
int ksm (int a,int b,int mod)
{
int ans=1;
while (b)
{
if (b&1) ans=1LL*ans*a%mod;
a=1LL*a*a%mod;
b>>=1;
}
return ans;
}
map <int,int> mp;
int exBSGS (int a,int b,int mod)
{
if (b==1) return 0;//情况1
int d=__gcd (a,mod),k=1,cnt=0;
while (d!=1)
{
if (b%d) return -1;//情况2
++cnt;
b/=d,mod/=d;
k=1LL*k*(a/d)%mod;//a前的系数
if (b==k) return cnt;//情况3
d=__gcd (a,mod);
}
mp.clear ();
int m=sqrt (mod)+1;
int s=b;
for (int i=0; i< m; i++)
mp[s]=i,s=1LL*s*a%mod;
int t=ksm (a,m,mod);
s=k;//a前的系数
for (int i=1; i<=m; i++)
{
s=1LL*s*t%mod;
if (mp.find (s)!=mp.end ()) return i*m-mp[s]+cnt;
}
return -1;
}
int main()
{
//freopen (".in","r",stdin);
//freopen (".out","w",stdout);
int a,b,mod; sc(a),sc(mod),sc(b);
while (a&&b&&mod)
{
int ans=exBSGS (a,b,mod);
if (ans!=-1) pr(ans);
else puts("No Solution");
sc(a),sc(mod),sc(b);
}
return 0;
}
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：(ex)BSGS”