BSGSと拡張BSGS

5074 ワード

BSGS
(BSGS)アルゴリズムは大股小歩とも呼ばれる((Baby-step-Giant-step))アルゴリズム(BSGS)アルゴリズムは主に以下の同余方程式[A^xequiv B(modp)]のうち((A,P)=1)、すなわち(A)と(P)の相互作用を解くために用いられる.
先行知識
オーラの定理(A^{varphi(p)}equiv 1(modp))による、(A^x(modp))のループ節は(varphi(p))である.すなわち,上記の方程式に解(x)があれば,必ず(xin[0,varphi(p)])があるので,(x)を列挙して解くことができる.
ガイド人
上は暴力的なやり方であり、(BSGS)はブロック化の考え方を利用して上のアルゴリズムの複雑度を(sqrt{varphi(p)})または(sqrt{varphi(p)}log;p)(map)メソッド(m=lceilsqrt{varphi(p)}rceil)では、いずれの(xin[0,varphi(p)])も(im-j(iin[1,m],jin[0,m])と表すことができる形式であれば、元の式は[A^{im-j}equiv B(modp)]と表すことができる
インプリメンテーション
そこで、右の(A^jB(jin[0,m]))を前処理して(hash)テーブルに保存します.次に左側の(iin[1,m])を列挙して(A^{im})を計算し、(hash)テーブルでクエリーします.列挙(i,j)の複雑さはすべて(sqrt{varphi(p)})であり、定数は(hash)テーブルの細部に依存し、一般的には(x)が最小であるため、(j)がより大きく、(i)がより小さくなることを望んでいる.したがって、(hash)テーブルに保存するときは、より大きな(j)を保持します.小さい頃から大きな列挙(i)まで、実行可能な答えに出会って直接出力すればいい.
例題
luogu3846
コード#コード#

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
#define int ll
mapma;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(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
",ans);

    return 0;
}

拡張BSGS
(BSGS)アルゴリズムには一定の限界がある((A,p)相互質()).拡張(BSGS)は、(A,p)が互いに質を持たない場合を処理することができる.
ガイド人
私たちはすでに(A,p)の互質の場合、(A,p)の非互質の場合、(A,p)の互質に変換すればよい.命令(d=gcd(A,p)).(dmid B)の場合、または(B=1)の場合、答えは(0)です.さもないとペ蜀の定理に基づいてきっと解けない.だから私たちは最初に(B=1)の状況を特判すればいいのです.後に(dmid B)を発見すれば無解を説明できる.だから今私たちは(dmid B)を仮定します.私たちは(A,B,P)を同時に1つの(d)で割った.すなわち[A^{x-1}frac{A}{d}equivfrac{B}{d}(mod\frac{p}{d})]を繰り返し、(d=1)まで同余方程式が得られる[A^{x−k}frac{ A^k}{prodlimits_{i=1}^kd_i}equivfrac{ B}{prodlimits_{i=1}^kd_i}(mod\frac{ p}{prodfrac{ p}{prodlimits_{i=1}^kd_i}]設定(p'=frac{ p}{{prodlimits_{i=1}^kd_i},B'=frac{ B'=frac{ Bd_i=1}^kd_i},B'=frac{ Bc{Bd_i},}{prodlimits_{i=1}^kd_i},C=frac{A^k}{prodlimits_{i=1}^kd_i},x'=x-k)原式は[A^{x'}Cequiv B'(modp')]となるそして(A,p')互質に変換する場合、普通の(BSGS)でできます.
例題
luogu4195
コード#コード#

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
#define int ll
mapma;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(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
",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
",ans);
    }

    return 0;
}

転載先:https://www.cnblogs.com/wxyww/p/BSGS.html

アルゴリズム(第4版)ノートPage 47.pdf

[HAOI2011] problem C