BSGS

算法又称大步小步算法

算法主要用于解以下同余方程

其中,即与互质

前置知识

根据欧拉定理，所以的循环节为.也就是说如果上面的方程有解，那么肯定有，所以我们可以枚举一下求解

推导

上面是暴力的做法，而就是利用分块的思想将上面的算法复杂度优化为(哈希表做法)或者(map)做法
我们令,那么任何一个都可以被表示成的形式
则原式可表示为$$

实现

所以先将右边预处理出来，存到表中。
然后枚举左边的计算出，并在表中查询。
枚举的复杂度都是，常数取决于表
有个细节的地方，一般我们都是要求最小的，所以我们希望更大，更小。所以在往表中存的时候，保留更大的那个。从小到大枚举，遇到可行答案直接输出即可。

例题

luogu3846

代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<map>
using namespace std;
typedef long long ll;
#define int ll
map<int,int>ma;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int B,A,L,P;
int qm(int x,int y) {
    int ret = 1;
    for(;y;y >>= 1,x = 1ll * x * x % P)
        if(y & 1) ret = 1ll * x * ret % P;
    return ret;
}

signed main() {
    P = read(),A = read(),B = read();
    ma.clear();
    int m = ceil(sqrt(P));
    int now = B;
    for(int i = 0;i <= m;++i) {
        ma[now] = i + 1;
        now = 1ll * now * A % P;
    }
    now = 1;
    int ans = -1;
    int kk = qm(A,m);
    for(int i = 1;i <= m;++i) {
        now = 1ll * now * kk % P;
        if(ma[now]) {
            ans =i * m - ma[now] + 1;
            break;
        }
    }
    if(ans == -1) puts("no solution");
    else printf("%lld\n",ans);

    return 0;
}

扩展BSGS

算法有一定的局限性互质。扩展可以处理不互质的情况。

推导

我们已经会了互质的情况，对于不互质的情况，只要将转化为互质即可。
令。
如果，那么要么,则答案为。否则根据裴蜀定理一定无解。所以我们只要在一开始的时候特判一下的情况。后面只要发现就可以说明无解。
所以现在我们假设。
我们将同时除以一个。即
$d = 1p'=\frac{p}{\prod\limits_{i=1}^kd_i},B'=\frac{B}{\prod\limits_{i=1}^kd_i},C=\frac{A^k}{\prod\limits_{i=1}^kd_i},x'=x-kA,p'BSGS$做了。

例题

luogu4195

代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<map>
using namespace std;
typedef long long ll;
#define int ll
map<int,int>ma;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int A,B,P;
int gcd(int x,int y) {
    return !y ? x : gcd(y,x % y);
}
int qm(int x,int y) {
    int ans = 1;
    for(;y;y >>= 1,x = 1ll * x * x % P) {
        if(y & 1) ans = 1ll * ans * x % P;
    }
    return ans;
}

signed main() {
    // freopen("in.in","r",stdin);
    while(1) {
        ma.clear();
        A = read(),P = read(),B = read();
        if(!A and !B and !P) return 0;
        if(B == 1) {
            puts("0");continue;//特判掉b=1的情况
        }
        int bz = 0,C = 1,d = gcd(A,P),K = 0;
        while(d != 1) {
            if(B % d) {
                puts("No Solution");
                bz = 1;break;
            }
            P /= d;
            B /= d;
            ++K;
            C = 1ll * C * (A / d) % P;
            d = gcd(A,P);
            if(B == C) {
                printf("%d\n",K);
                bz = 1;
                break;
            }
        }
        if(bz == 1) continue;
        int m = ceil(sqrt(P));
        int now = B;
        for(int i = 0;i <= m;++i) {
            ma[now] = i + 1;
            now = 1ll * now * A % P;
        }
        now = C;
        int ans = -1;
        int kk = qm(A,m);
        for(int i = 1;i <= m;++i) {
            now = 1ll * now * kk % P;
            if(ma[now]) {
                ans =i * m - ma[now] + 1 + K;
                break;
            }
        }
        if(ans == -1) puts("No Solution");
        else printf("%lld\n",ans);
    }

    return 0;
}