前言
关于高次同余方程，有 \(a^x \equiv b(\text{mod} \ p)\) 和 \(x^a \equiv b(\text{mod} \ p)\) 两种类型，后者计算起来较为麻烦，下文就分别记述这两种高次同余方程。
离散对数问题
离散对数问题是在模 \(p\) 意义下求解 \(\log_ab\)，这等价于形如
\[a^x \equiv b(\text{mod} \ p) \]的高次同余方程，其中 \(x\) 即为 \(\log_ab\)，\(x\) 是一个非负整数。
当 \(a \perp b\) 时，我们可以采用 BSGS 算法解决；当 \(a \not\perp b\) 时，可以采用 exBSGS 算法求解。
BSGS
大步小步算法，英文名为 Baby Step Giant Step，简称 BSGS。适用于 \(a\perp p\) 的情况。
算法流程
由扩展欧拉定理得
\[a^x \equiv a^{x \mod \varphi(p)}(\text{mod} \ p) \]所以 \(a^x\) 模 \(p\) 意义下的循环节就是 \(\varphi(p)\)，又因 \(\varphi(p) < p\)，所以考虑 \(x\in[0,p]\) ，一定能找到最小整数 \(x\)。自此，问题缩小到了 \(O(p)\) 级别。如果 \(p\leq 2^{32}\)，那就超时了。这时候就要请出我们今天的主角----根号平衡闪亮登场！
我们令 \(x = im-j\)，其中 \(m=\lceil \sqrt{p} \ \rceil , i\in[1,m],j\in[0,m-1]\)。这样分配，\(im-j\) 就能取遍 \([1,p]\) 了，如果 \(x=0\)，说明 \(b=1\)，特判一下就行了。
我们把上式转换一下，则有
\[a^{im-j} \equiv b(\text{mod} \ p) \]因为 \(a\perp p\) ，所以
\[(a^{m})^i \equiv ba^j(\text{mod} \ p) \]是一个等价转换（除回去模数不变）。
然后枚举 \(i,j\)。
-
先枚举 \(j\)，把 \((ba^j \ \text{mod} \ p,j)\) 插入一个 Hash 表。如果 \(ba^j \ \text{mod} \ p\) 出现相等的情况，为了求最小解，显然用更大的 \(j\) 替代小的解。
-
然后枚举 \(i\) ，计算 \((a^m)^i \ \text{mod} \ p\)，到 Hash 表中判断是否有相等的 key，因为 \(i\times m\) 的变化量是比 \(j\) 大的，所以我们找到第一个就可以结束程序，最小的 \(x=im-j\) 就出来了。
这样，枚举 \(i,j\) 的次数都是 \(\sqrt p\) 的，总算法的复杂度也就是 \(O(\sqrt{p\ })\) 的。
map <int,int> Hash;
signed main()
{
mod = read() , a = read(), b = read();
if(b == 1) { return printf("0"),0; }//特判一下
m = ceil(sqrt(mod));
Hash[b] = 0/*j取0,ba^j就是b*/ , t = b;
for(re int i=1;i<m;i++)//枚举ba^j
{
t = t * a % mod;
Hash[t] = i;
}
val = ksm(a,m) , t = 1;
for(re int i=1;i<=m;i++)//枚举(a^m)^i
{
t = t * val % mod;
if(Hash.count(t)) { return printf("%lld",i*m-Hash[t]),0; }//有值直接输出
}
printf("no solution");
return 0;
}
exBSGS
当 \(a\not\perp p\) 的时候，我们的 exBSGS 就要出场了。
化未知为已知，我们思考怎么操作能让 \(a,p\) 互质。
首先，原方程可以写作
\[a \cdot a^{x-1} \equiv b(\text{mod} \ p) \]的形式，这就是把 \(a\) 提出来的一个过程。这也等价于求 \(a\cdot a^{x-1} + py = b\) 的解。
令 \(d_1 = \gcd(a,p)\)。如果 \(d_1\nmid b\)，则原方程无解。
否则由同余的性质得，同余方程就变成
\[\frac{a}{d_1}a^{x-1} \equiv \frac{b}{d_1}(\text{mod} \ \frac{p}{d_1}) \]这启发我们要不断提取 \(a\) 出来，直到 \(a\) 和模数互质。
设 \(d_2 = \gcd(a,\frac{p}{d_1})\)，然后重复上述操作，直到互质。
当 \(a\perp \frac{p}{d_1\dots d_k}\) 时，我们就可以套用 BSGS 了。设 \(D = \prod_{i=1}^kd_i\)，原方程就变成了形如
\[\frac{a^k}{D}a^{x-k} \equiv \frac{b}{D}(\text{mod} \ \frac{p}{D}) \]的形式。因为 \(a\perp \frac{p}{D}\)，所以 \(\frac{a^k}{D}\perp \frac{p}{D}\)，那么就可以求个逆元，把 \(\frac{a^k}{D}\) 消掉，然后再套一个 BSGS 就可以了。
注意，BSGS 结束后算出来的是 \(x-k\) 而非 \(x\)，别忘了把 \(k\) 加上。
实际上，\(\frac{a^k}{D}\) 也可以不用求逆元，只要在 BSGS 枚举 \(i\) 的时候把初值设为 \(\frac{a^k}{D}\) 即可。
code
il int BSGS(int a,int b,int mod,int k)
{
Hash.clear();
m = ceil(sqrt(mod));
Hash[b] = 0 , t = b;
for(re int i=1;i<m;i++)
{
t = 1ll * t * a % mod;
Hash[t] = i;
}
val = ksm(a,m,mod) , t = k;//初值设为k
for(re int i=1;i<=m;i++)
{
t = 1ll * t * val % mod;
if(Hash.count(t)) { return i*m-Hash[t]; }
}
return -1;
}
il void exBSGS()
{
a = read() , mod = read() , b = read();
if(!a && !mod && !b) exit(0);
a %= mod , b %= mod;//先模再特判
if(b == 1 || mod == 1) { puts("0"); return ; }
cnt = d = 0 , k = 1;
while((d=gcd(a,mod)) != 1)
{
if(b % d) { puts("No Solution"); return; }//无解情况
cnt++;//不知道为什么这个放在if上面就wa一个点，很怪
b /= d , mod /= d;//逐渐往下找
k = 1ll * k * (a / d) % mod;//a^{x-k}前的系数
if(k == b) { printf("%d\n",cnt); return ; }//k==b说明a^{x-k} = 1,x=k
}
ans = BSGS(a,b,mod,k);
if(ans == -1) puts("No Solution");
else printf("%d\n",ans+cnt);
}