浅谈BSGS和EXBSGS - 某邓_Duck

我的 BSGS 和各位犇犇的差不多，但是不需要求逆元

Luogu [ TJOI2007 ] 可爱的质数

给定一个质数 pp，以及一个整数 bb，一个整数 nn，现在要求你计算一个最小的非负整数 ll，满足 bl≡n(modp)bl≡n(modp)。

仅一行，有 33 个整数，依次代表 p,b,np,b,n。

仅一行，如果有 ll 满足该要求，输出最小的 ll，否则输出 no solution。

样例输入 #1

5 2 3

样例输出 #1

3

数据规模与约定

• 对于所有的测试点，保证 2≤b,n<p<2312≤b,n<p<231。

Baby Steps Giant Steps 详解

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

其实可以优化到O(p–√)O(p)，设 m=⌈p–√⌉,r=b%mm=⌈p⌉,r=b%m

于是我们可以将 原式写成

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

只需将式子改成

解决了问题

我们考虑找到一个 kk 和 一个 rr 使得上述式子成立，这个并不难

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

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

然后把右边式子的值哈希存下，枚举左边的 k(1≤k≤m)k(1≤k≤m)

对于左边枚举求出的值看看哈希数组是否存在对应的右边的值，如果有，那么就是一个解

搞出一个最小的解好像也不是很难吧.....

时间复杂度 O(m)O(m) ，也就是 O(p–√)O(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,ba,p,b，求满足 ax≡b(modp)ax≡b(modp) 的最小自然数 xx 。

每个测试文件中包含若干组测试数据，保证 ∑p–√≤5×106∑p≤5×106。

每组数据中，每行包含 33 个正整数 a,p,ba,p,b 。

当 a=p=b=0a=p=b=0 时，表示测试数据读入完全。

对于每组数据，输出一行。

如果无解，输出 No Solution，否则输出最小自然数解。

样例输入 #1

5 58 33 2 4 3 0 0 0

样例输出 #1

9 No Solution

对于 100%100% 的数据，1≤a,p,b≤1091≤a,p,b≤109 或 a=p=b=0a=p=b=0。

扩展 Baby Steps Giant Steps 详解

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

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

注意，操作时如果两边值相等了，答案就是 cntcnt

然后就是个普通 BSGS ,变了一点点，左边需要乘上 a′a′，其他都是一模一样的

求出答案之后答案要加上 cntcnt ,因为我们求出的是 x−cntx−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;
}