参考资料

• 离散对数 - OI Wiki

题意简述

给定质数 $p$ 与整数 $b,n$，求最小的非负整数 $l$，使 $b^l\equiv n\pmod p$，无解则报告。

解题思路

设 $m=\lceil\sqrt p\rceil$。$p$ 为质数，$b\not\equiv 0$ 时 $\gcd(b,p)=1$，可用 BSGS（Baby-Step Giant-Step，大步小步）。

把 $l$ 写作 $l=im-j$（$0\le j<m$），代入 $b^l\equiv n$ 得：

$$b^{im}\equiv n\cdot b^{j}\pmod p$$

两侧分别枚举：

1. 小步：枚举 $j$ 从 $0$ 到 $m-1$，将 $n\cdot b^{j}$ 连同 $j$ 存入哈希表；
2. 大步：枚举 $i$ 从 $1$ 到 $m$，算出 $b^{im}$ 查表，命中即得 $l=im-j$。

若有解，最小解必小于 $p\le m^2$，故枚举范围足以覆盖。$i$ 自小到大、哈希表对相同键保留较大的 $j$，首个命中即最小的 $l$。$l=0$（即 $n\equiv 1$）单独特判。

时间复杂度为 $O(\sqrt p)$。

参考代码

521 Bcpp

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
ll bsgs(ll b,ll n,ll p)
{
	if(n==1)return 0;
	unordered_map<ll,ll> mp;
	ll m=sqrt(p),k=n;
	for(ll j=0;j<m;j++)
	{
		mp[k]=j;
		k=k*b%p;
	}
	ll t=1;
	for(ll i=0;i<m;i++)t=t*b%p;
	k=1;
	for(ll i=1;i<=m;i++)
	{
		k=k*t%p;
		if(mp.count(k))return i*m-mp[k];
	}
	return -1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll p,b,n;
	cin>>p>>b>>n;
	ll res=bsgs(b,n,p);
	if(res==-1)cout<<"no solution"<<'\n';
	else cout<<res<<'\n';
	return 0;
}