BSGS

BSGS算法(Baby Step Giant Step)

用来求解高次同余方程： 给定$a,b,p$,$满足a,p$互质，求满足$a^x \equiv b(\bmod p)$的最小非负整数$x$

思路

由欧拉定理：$a^x\equiv a^{a \bmod \psi(p)}\bmod p$，可以知道$a^x\bmod p$意义下的最小循环节为$\psi(p)$,因为$\psi(p)<p$,所以可以考虑$x\in[0,p]$必定可以找到最小整数$x$ 令$x=i*m-j$,其中$m=ceil(\sqrt{(p)}),i\in[1,m],j\in[0,m-1]$,则$a^{im-j} \equiv b(\bmod p)$ 两边同时乘$a^{j}$,可得$(a^m)^i \equiv ba^j (\bmod p)$ 先枚举$j$，将$(ba^j,j)$放入哈希表，如果$key$重复，会用更大的$j$进行替换旧的 再枚举$i$,计算$(a^m)^i$，到哈希表中查找是否有相等的$key$,找到的第一个就结束为最小的$x=im-j$

代码

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

//求a^x同余b(mod p)的最小非负整数x
LL bsgs(LL a,LL b,LL p){
    a%=p;b%=p;
    if (b==1) return 0;//x=0
    LL m=ceil(sqrt(p));
    LL t=b;
    unordered_map<LL,LL> hash;
    hash[b]=0;
    for(int j=1;j<m;j++){
        t=t*a%p;//b*a^j
        hash[t]=j;
    }
    LL mi=1;
    for(int i=1;i<=m;i++)
        mi=mi*a%p;//a^m
    t=1;
    for(int i=1;i<=m;i++){
        t=t*mi%p;
        if (hash.count(t))
            return i*m-hash[t];
    }
    return -1;//无解
}

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    int p,b,n;
    cin>>p>>b>>n;
    int t= bsgs(b,n,p);
    if (t==-1) pr("no solution")
    else pr(t)

    return 0;
}

扩展BSGS算法

https://www.luogu.com.cn/problem/P4195 求满足$a^x\equiv b(\bmod p)$的最小非负整数$x$,设$d_1=gcd(a,p)$,如果$d_1不能整除b$,则原方程无解。不停的判断，直到$a$与$\frac{p}{d_1d_2...d_k}$互质，记$D=\prod_{i=0}^{k}d_i$,原方程变为$\frac{a^k}{D}a^{x-k} \equiv \frac{b}{D} (\bmod \frac{P}{D})$ BSGS:$\frac{a^k}{D}a^{im-j} \equiv \frac{b}{D} (\bmod \frac{P}{D})$,即$Aa^{im-j} \equiv B' (\bmod P')$

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

LL gcd(LL a,LL b){
    return b? gcd(b,a%b):a;
}

//求a^x同余b(mod p)的最小非负整数x

LL exbsgs(LL a, LL b, LL p) {
    a %= p;
    b %= p;
    if (b == 1 || p == 1) return 0;
    LL d, k = 0, A = 1;
    while (true) {
        d = gcd(a, p);
        if (d == 1) break;//说明a,p互质了
        if (b % d) return -1;//系数b不能整除最大公约数
        k++;
        b /= d;
        p /= d;
        A = A * (a / d) % p;
        if (A == b) return k;
    }
    LL m = ceil(sqrt(p));
    LL t = b;
    unordered_map<LL, LL> h;
    h[b] = 0;
    for (int j = 1; j < m; j++) {
        t = t * a % p;//求b*a^j
        h[t] = j;
    }
    LL mi = 1;
    for (int i = 1; i <= m; i++)
        mi = mi * a % p;//求a^m

    t = A;
    for (int i = 1; i <= m; i++) {
        t = t * mi % p;//求（a^m）^i
        if (h.count(t))
            return i * m - h[t] + k;
    }
    return -1;

}

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    LL a,p,b;
    while (cin>>a>>p>>b){
        if (a==0||p==0|b==0) break;
        LL t= exbsgs(a,b,p);
        if (t==-1) pr("No Solution")
        else
        pr(t)
    }

    return 0;
}