BSGS
当由扩展欧拉定理
$$
a^x \equiv
\left\\{
\begin{array}{ll}
a^x , x < \phi(n) & ,(\mod n) \\\
a^{(x \mod \phi(n))\ +\ \phi(n)} , x \ge \phi(n) & ,(\mod n) \\\
\end{array}
\right.
$$
可以知道我们 $a$ 的幂的循环节长度是 $ \le \phi(p)$ 的,而由于我们 $\phi(p) < p$ 。所以我们可以通过枚举$a^{[1..p]}$ 来得到高次同余方程的最小正整数解。但是,这样枚举的复杂度显然是很高的,所以我们考虑进行分块枚举。
假设 $gcd(a,p) == 1$,我们将要枚举的 $[1..p]$ 分成 $\lceil{\sqrt{p}}\rceil$ 个区间,设 $m=\lceil{\sqrt{p}}\rceil , x = i\times m - j,$其中 $ i\in[1,m],j\in [1,m)$ 。则有
$$
\begin{array}{ll}
& a^x = a^{im - j } \equiv b (\mod p) \\\
& \Rightarrow a^{im} \equiv ba^j (\mod p)
\end{array}
$$
我们枚举$a^{[1..p]}$ ,实际上就等价于从小到大枚举 $i$ ,对于每个$i$ ,再枚举 $j$ 。如果直接枚举$i,j$ ,复杂度还是 $O(n)$ ,但是如果我们先枚举 $j$ ,并将结果经过哈希将$<ba^j,j\>$存起来(如果对应的 $ba^j$ 冲突,则保留大的 $j$ ),再去枚举 $i$ ,可以发现我们枚举 $i$ 只要 $O(\sqrt n)$ ,查是否有同余的 $ba^j$ 只用 $O(1)$ 。此时复杂度就降到了$O(\sqrt n)$ 。
注意,BSGS的前提是$gcd(a,p) == 1$,因为只有$a、p$互质的时候才可以将同余式两边左右同时乘 $a^j$ 。
对应板子题 : P3846 [TJOI2007] 可爱的质数/【模板】BSGS
C++ 代码
#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int (a) = (b) ; (a) < (c) ; ++(a))
using namespace std;
using ll = long long ;
using pii = pair<int,int> ;
inline int gcd(int a,int b){
return b ? gcd(b,a%b) : a ;
}
inline int qpow(int a,int b,int p){
int res = 1 ;
while (b){
if (b & 1) res = 1ll * res * a % p ;
b >>= 1;
a = 1ll * a * a % p ;
}
return res ;
}
int main(){
int p,a,b,tmp,m;
cin >> p >> a >> b ;
if (gcd(a,p) ^ 1) return cout << "no solution",0;
a %= p,b %= p ;
if (b == 1) return cout << 0,0 ;
m = ceil(__builtin_sqrt(p));
unordered_map<int,int>M ;
M[b] = 0 ;
tmp = b;
rep(j,1,m) M[tmp = 1ll * tmp * a % p] = j ;
tmp = qpow(a,m,p);
a = 1 ;
rep(i,1,m + 1) {
a = 1ll * a * tmp % p ;
if (M.count(a))
return cout << i * m - M[a],0;
}
cout << "no solution";
return 0;
}
EXBSGS
EXBSGS就是可以对 $gcd(a,p) \ne 1$ 时进行高次同余方程的计算。
对于$gcd(a,p) \ne 1$的情况,通过将原式$a^x \equiv b (\mod p)$ 转换成 $ax + by = c$ 形式即 $a a^{x-1 } + p y = b$ ,可以有裴属定理得到,方程有整数解当且仅当 $b | gcd(a,p)$ ,假设有整数解,我们可以将整个式子除于 $d_1 = gcd(a,p)$ ,即$\frac{a}{d_1}a^{x-1} +\frac{p}{d_1}y = \frac{b}{d_1}$ 。然后再回到判断 $a、\frac{p}{d_1}$ 是否互质的情况 ,如果互质,就进行BSGS;否则继续除.... 。主要的目的就是使$a、p$互质 。
需要注意的是,假设我们在判断出互质后,有$\frac{a^k}{D} a^{x-k} \equiv \frac{b}{D} (\mod \frac{p}{D})$ 其中 $D = d_1d_2…d_k$ ,此时我们放入$BSGS$的参数是 $(a^{x-k},\frac{b}{D} \times (\frac{a^k}{D})_{inv},\frac{p}{D})$ 。 如果有解,得到是 $x-k$ 后的结果,最后还要 + $k$ 。
算法总体复杂度应该还是 $O(\sqrt n)$ ,虽然增加了使$a、p$互质的步骤,但该步骤的复杂度应该也是对数级别的,相较于根号,对数复杂度还是可以忽略的。
对应板子题 MOD - Power Modulo Inverted , P4195 【模板】扩展 BSGS/exBSGS
C++代码
#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int (a) = (b) ; (a) < (c) ; ++(a))
using namespace std;
using ll = long long ;
using pii = pair<int,int> ;
char CH,NUM[40];bool F;int LEN;
template <typename T>
inline void R(T &x){
x = 0,F = 0,CH = getchar();
while (CH < '0' || CH > '9' ){if (CH == '-') F = 1;CH = getchar();}
while (CH >= '0'&& CH <= '9' ){x = (x << 3) + (x << 1) + (CH & 15) ; CH = getchar() ;}
if (F) x = -x ;
}
template <typename T>
inline void W(T x) {
if (!x){ putchar('0'); return ;} LEN = 0;
if (x < 0) putchar('-'), x = -x;
while(x) NUM[++LEN] = (x - x / 10 * 10 ) + 48, x /= 10;
while(LEN) putchar(NUM[LEN--]);
}
inline int gcd(int a,int b){
return b ? gcd(b,a % b) : a ;
}
inline int qpow(int a,int b,int p){
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % p ;
b >>= 1;
a = 1ll * a * a % p ;
}
return res ;
}
inline void exgcd(int a,int b,ll &x,ll &y){
if (!b) x = 1,y = 0;
else exgcd(b,a % b,y,x),y -= a / b * x;
}
inline int exbsgs(int a,int b,int p){
a %= p,b %= p;
if (b == 1 || p == 1) return 0 ;
int d,A = 1,k = 0;
while ((d = gcd(a,p)) ^ 1){
if (b % d) return -1 ;
b /= d,p /= d,A = 1ll * A * (a / d) % p,++ k;
if (A == b) return k ;
}
ll inv,tmp;
unordered_map<int,int> M ;
exgcd(A,p,inv,tmp),inv = (inv % p + p) % p;
int m = ceil(__builtin_sqrt(p)),cur = 1ll * inv * b % p ;
M[cur] = 0;
rep(i,1,m) M[cur = 1ll * cur * a % p] = i ;
cur = qpow(a,m,p);
A = 1;
rep(i,1,m + 1)
if (M.count(A = 1ll * A * cur % p))
return i * m - M[A] + k ;
return -1 ;
}
int main(){
int a,b,p,res;
while (true){
R(a),R(p),R(b);
if (!(a | b | p)) break ;
res = exbsgs(a,b,p);
if (~res) W(res),pc('\n');
else puts("No Solution");
}
return 0;
}