我的 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<pair<ll, int> > 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<pair<ll, int> > 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; } 
