浅谈BSGS和EXBSGS

我的 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 

数据规模与约定

• 对于所有的测试点，保证 (2le b,n < p<2^{31})。

Baby Steps Giant Steps 详解

注意到互质，根据欧拉定理，我们易得(l< p)，枚举的时间复杂度为(O(p))

其实可以优化到(O(sqrt{p}))，设 (m=lceil sqrt{p}rceil,r=b%m)

于是我们可以将 原式写成

[b^{km+r}equiv n(mod;p)\ b^{km}equiv nb^{-r}(mod;p) ]

右边好像要求逆元啊，我们不想求逆元，怎么办呢？

只需将式子改成

[b^{km-r}equiv n(mod;p)\ b^{km}equiv nb^{r}(mod;p) ]

解决了问题

我们考虑找到一个 (k) 和 一个 (r) 使得上述式子成立，这个并不难

首先枚举 (r) ，显然有 (r(1leq rleq m)) 注意这里和广大打法不同

因为广大打法是枚举余数，这里枚举的是相反的

然后把右边式子的值哈希存下，枚举左边的 (k(1leq 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 ple 5times 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%) 的数据，(1le a,p,b≤10^9) 或 (a=p=b=0)。

扩展 Baby Steps Giant Steps 详解

注意到不互质，那我们就要想办法让它互质

[a^xequiv b(mod;p)\ a^x-kp=b\ 设 d=gcd(a,p)\ 若 d|b 不成立，则无解\ 式子除 d 得 a^{x-1}frac a d- kfrac p d=frac b d\ 改记为a^{x-1}a'- kp'=b'\ 即 a^{x-1}a'equiv b'(mod; p') ]

如此反复，直到互质为止，差不多就是

[a^{x-cnt}a'equiv b'(mod; p') ]

注意，操作时如果两边值相等了，答案就是 (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; }