我的 BSGS 类似于你的本，但不需要逆元
Luogu [ TJOI2007 ] 可爱的质数
原题展现
题目描述
给定一个质数 \(p\)，还有一个整数 \(b\)，一个整数 \(n\)，现在要求你计算最小的非负整数 \(l\)，满足 \(b^l \equiv n \pmod p\)。
输入格式
仅一行，有 \(3\) 依次代表整数 \(p, b, n\)。
输出格式
只有一行，如果有 \(l\) 满足该要求，输出最小的 \(l\)，否则输出 no solution。
样例 #1
样例输入 #1
5 2 3样例输出 #1
3数据规模和协议
- 保证所有试验点 \(2\le b,n < p<2^{31}\)。
Baby Steps Giant Steps 详解
根据欧拉定理，我们很容易注意到互质\(l< p\)，枚举的时间复杂度为\(O(p)\)
其实可以优化\(O(\sqrt{p})\)，设 \(m=\lceil \sqrt{p}\rceil,r=b\%m\)
所以我们可以 原式写成
右边好像要逆元。我们不想要逆元。我们该怎么办？
只需将公式改成
解决了问题
我们考虑找一个 \(k\) 和 一个 \(r\) 建立上述公式并不难
首先枚举 \(r\) ，显然有 \(r(1\leq r\leq m)\) 注意这里和广大打法不一样
因为大多数游戏都是枚举余数，这里的枚举是相反的
然后保存右边风格的值哈希，枚举左边 \(k(1\leq k \leq m)\)
对于左枚举的值，看看哈希数组是否有相应的右值。如果是这样，那就是一个解决方案
做出最小的解似乎并不难...
时间复杂度 \(O(m)\) ，也就是 \(O(\sqrt{p})\)
然后注意打很多特判。
上一下码风巨丑的代码
inline ll ksc(ll x, ll y, const ll& p) { return (x * y - (ll)((long double)x / p * y) * p p) % p; } vector > v[ 100013]; inline ll BSGS(ll a, ll b, const ll&p) { if (b == 1) { if (a == 0) return -1; return 1; } if (b == 0) { if (a == 0) return 1; return -1; } if (a == 0) { return -1; } ll m = ceil(sqrt(p)), cnt = 1, res = 1; for (int r = 1; r <= m; r ) { cnt = ksc(cnt, a, p);///这个龟速乘不是龟速乘 v[(ksc(cnt, b, p)) % mod].push_back(make_pair(ksc(cnt, b, p), r)); } for (int k = 1; k <= m; k ) { res = ksc(cnt, res, p); ll id=res%mod; if (v[id].size()) { for (int j = v[id].size() - 1; j >= 0; j--) { if (v[id][j].first ==res) { return m * k - v[id][j].second; } } } } return -1; } SPOJ3105 MOD
原题展现
题目描述
给定 \(a,p,b\)，求满足 \(a^x≡b \pmod p\) 的最小自然数 \(x\) 。
输入格式
每个测试文件包含几组测试数据，以确保 \(\sum \sqrt p\le 5\times 10^6\)。
在每组数据中，每行包含 \(3\) 个正整数 \(a,p,b\) 。
当 \(a=p=b=0\) 时间表示测试数据已完全读入。
输出格式
输出一行每组数据。
若无解，输出 No Solution，否则，输出最小自然数解。
样例 #1
样例输入 #1
5 58 33 2 4 3 0 0 0样例输出 #1
9 No Solution数据范围
对于 \(100\%\) 的数据，\(1\le a,p,b≤10^9\) 或 \(a=p=b=0\)。
扩展 Baby Steps Giant Steps 详解
注意到不互质，就要想办法让它互质
如此反复，直到互质为止，差不多就是
注意，操作时如果两边值相等了，答案就是 \(cnt\)
然后就是个普通 BSGS ,变了一点点，左边需要乘上 \(a'\)，其他都是一模一样的
求出答案之后答案要加上 \(cnt\) ,因为我们求出的是 \(x-cnt\)
本题时限高达 4s ，就算不写哈希用 map 也能通过
参考如下实现
vector > v[ 1000013];
int vis[1000003];
inline ll exBSGS(ll a,ll b,ll p)
{
memset( vis,0,sizeof(vis));
if(p==0)return -1;
if(p==1)
{
if(b==0)return 0;
return -1;
}
if (b == 1) {
if (a == 0)
return -1;
return 1;
}
if (b == 0) {
if (a == 0)
return 1;
return -1;
}
if (a == 0) {
return -1;
}
ll ak=0,t=1,d=gcd(a,p);
while(d!=1)
{
ak++;
t*=a;
t/=d;
p/=d;
if(b%d!=0)return -1;
b/=d;
if(t%p==b%p)return ak;
d=gcd(a,p);
t%=p;
}
ll m = ceil(sqrt(p)), res=t%p,cnt=1;
for (int r = 1; r <= m; r++) {
cnt = ksc(cnt, a, p);
ll hash=(ksc(cnt, b, p)) % mod;
if(vis[hash]==0)
{
vis[hash]=1;
v[hash].clear();
}
v[hash].push_back(make_pair(ksc(cnt, b, p), r));
}
for (int k = 1; k <= m; k++) {
res = ksc(cnt, res, p);
ll hash=res%mod;
if (vis[hash])
{
for (int j = v[hash].size() - 1; j >= 0; j--)
{
if (v[hash][j].first ==res)
{
return m * k - v[hash][j].second+ak;
}
}
}
}
return -1;
} 大部分 BSGS 题都很明显，随便挑了几道
P4884 多少个 1？
原题展现
题目描述
给定整数 \(K\) 和质数 \(m\)，求最小的正整数 \(N\)，使得 $ 11\cdots1\((\)N$ 个 \(1\))\(\equiv K \pmod m\)。
说人话：就是 \(111\cdots 1111 \bmod m = K\)。
输入格式
第一行两个整数，分别表示 \(K\) 和 \(m\)。
输出格式
一个整数，表示符合条件最小的 \(N\)。
样例 #1
样例输入 #1
9 17样例输出 #1
3提示
\(30\%\) 的数据保证 \(m\leq 10^6\)。
\(60\%\) 的数据保证 \(m\leq 5\times 10^7\)。
\(100\%\) 的数据保证 \(6\leq m\leq 10^{11}\)，\(0< K< m\)，保证 \(m\) 是质数。
解法
将式子乘九，再加一，得到一个式子
然后 BSGS 即可
[SDOI2013] 随机数生成器
原题展现
题目背景
小 W 喜欢读书，尤其喜欢读《约翰克里斯朵夫》。
题目描述
最近小 W 准备读一本新书，这本书一共有 \(p\) 页，页码范围为 \(0 \sim p-1\)。
小 W 很忙，所以每天只能读一页书。为了使事情有趣一些，他打算使用 NOI2012 上学习的线性同余法生成一个序列，来决定每天具体读哪一页。
我们用 \(x_i\) 来表示通过这种方法生成出来的第 \(i\) 个数，也即小 W 第 \(i\) 天会读哪一页。这个方法需要设置 \(3\) 个参数 \(a,b,x_1\)，满足 \(0\leq a,b,x_1\lt p\)，且 \(a,b,x_1\) 都是整数。按照下面的公式生成出来一系列的整数：
其中 \(\bmod\) 表示取余操作。
但是这种方法可能导致某两天读的页码一样。
小 W 要读这本书的第 \(t\) 页，所以他想知道最早在哪一天能读到第 \(t\) 页，或者指出他永远不会读到第 \(t\) 页。
输入格式
本题单测试点内有多组测试数据。
第一行是一个整数 \(T\)，表示测试数据组数。
接下来 \(T\) 行，每行有五个整数 \(p, a, b, x_1, t\)，表示一组数据。
输出格式
对于每组数据，输出一行一个整数表示他最早读到第 \(t\) 页是哪一天。如果他永远不会读到第 \(t\) 页，输出\(-1\)。
样例 #1
样例输入 #1
3
7 1 1 3 3
7 2 2 2 0
7 2 2 2 1样例输出 #1
1
3
-1提示
对于全部的测试点，保证：
- \(1 \leq T \leq 50\)。
- \(0 \leq a, b, x_1, t \lt p\)，\(2 \leq p \leq 10^9\)。
- \(p\) 为质数。
解法
推式子，我还没做，等几天吧...
