题解 P4195 【【模板】exBSGS/Spoj3105 Mod】
ButterflyDew · · 题解
之前题解被叉了，upt了一下，应该没问题了吧...?
-
BSGS
前置知识：欧拉定理：若正整数
a,p 互质，那么有a^{\varphi(p)}\equiv 1\pmod p 给定
a,p,b ，其中(a,p)=1 ，求最小自然数解x a^x\equiv b\pmod p 根据欧拉定理，
a^x 最多只有\varphi(p) 个，所以我们可以只考虑x\in [0,\varphi(p)) 的情况。首先特判几种情况：
-
b=1$时，$x=0 -
a=0$时，若$b\not=0$，则无解，否则有解$x=1 -
b=0$时，若$a\not=0$，则无解，否则有解$x=1
注意这个特判是按顺序的，因为我们这里规定
0^0=1 然后考虑对
x 进行分块，具体的，可以对x 进行拆分\begin{aligned}&a^{ti-k}\equiv b\pmod p\\&a^{ti}\equiv b\times a^k\pmod p\\\end{aligned} 取
t=\sqrt n ，然后枚举k\in [0,t-1] ，并把所有的ba^k 插入\mathcal {Hash} 表中。然后枚举
i\in [1,t] ，在\mathcal{Hash} 表中查询a^{ti} ，看是否有k 可以匹配上。 -
-
exBSGS
给定
a,p,b ，求最小自然数解x a^x\equiv b\pmod p 一样，首先考虑特判几种情况：
-
b=1$时，$x=0 -
a=0$时，若$b\not=0$，则无解，否则有解$x=1 -
方程变成了这样
a^x\equiv 0\pmod p 稍微转换一下
k=\frac{a^x}{p},k\in \mathbb Z 发现直接枚举
x 就可以了，把(a,p) 除掉，然后看什么时候p=1 ，就返回x ，如果(a,p)=1 ，那么直接无解。少了互质的条件，考虑构造互质。
和
b=0 时一个思路，考虑先枚举一部分x a\times a^{x-1}\equiv b\pmod p 稍微动一动式子
a\times a^{x-1}-yp=b 根据裴蜀定理，如果
(a,p)\nmid b ，那么返回无解否则把整个式子除
(a,p) ，变成\begin{aligned}&\frac{a}{(a,p)}a^{x-1}-y\frac{p}{(a,p)}=\frac{b}{(a,p)}\\&\frac{a}{(a,p)}a^{x-1}\equiv \frac{b}{(a,p)}\pmod {\frac{p}{(a,p)}}\end{aligned} 考虑令
A=a,B=\frac{b}{(a,p)},C=\frac{a}{(a,p)},P=\frac{p}{(a,p)} 那么式子成了
CA^x\equiv B\pmod P 继续递归即可，如果某一步
(A,P)=1 ，就用普通BSGS搞一下C$显然不影响我们进行普通$BSGS 注意一点，如果某一步
C=B 了，直接返回枚举的x ，因为我们需要求最小自然数解。枚举的
x 也就是递归深度是\log 级别的，所以复杂度没问题 -
Code:
#include <cstdio>
#include <cctype>
#include <cmath>
#include <unordered_map>
const int SIZE=1<<21;
char ibuf[SIZE],*iS,*iT;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)
template <class T>
inline void read(T &x)
{
x=0;char c=gc();
while(!isdigit(c)) c=gc();
while(isdigit(c)) x=x*10+c-'0',c=gc();
}
std::unordered_map <int,int> Hash;
#define mul(a,b,p) (1ll*(a)*(b)%p)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int exBSGS(int a,int b,int p)
{
a%=p,b%=p;
if(b==1) return 0;
if(!b&&!a) return 1;
if(!a) return -1;
if(!b)
{
int ret=0,d;
while((d=gcd(a,p))!=1)
{
++ret,p/=d;
if(p==1) return ret;
}
return -1;
}
int ret=0,A=a,B=b,P=p,C=1,d;
while((d=gcd(A,P))!=1)
{
if(B%d) return -1;
P/=d,B/=d;
C=mul(C,A/d,P);
++ret;
if(C==B) return ret;
}
Hash.clear();
int f=1,t=sqrt(P)+1;
for(int i=0;i<t;i++)
{
Hash[mul(f,B,P)]=i;
f=mul(f,A,P);
}
int tf=f;
f=mul(f,C,P);
for(int i=1;i<=t;i++)
{
if(Hash.find(f)!=Hash.end()) return ret+i*t-Hash[f];
f=mul(f,tf,P);
}
return -1;
}
int main()
{
int a,p,b;read(a),read(p),read(b);
while(a&&p&&b)
{
int ans=exBSGS(a,b,p);
if(~ans) printf("%d\n",ans);
else puts("No Solution");
read(a),read(p),read(b);
}
return 0;
}