BSGSアルゴリズム学習小記(大股小歩アルゴリズム)

概要
まず1つの式xy≡z(modp)を見て、zは質量数で今xとzだけを知っていて、yを要求します.ステップステップアルゴリズム(BSGS,Baby Steps Giant Steps)はこの問題を解決する.
アルゴリズムフロー
暴捜の列挙範囲
Ferma小定理:xp−1≡1に基づいた.yがp−1に列挙され,列挙を続けるとループが生じる.だから、暴捜でyの列挙範囲は0......p-1である.
暴力捜査を最適化する方法
列挙したyをブロックで解決できるかどうか考えてみましょう.yをp−1−−−−−−−√に分けて別々に行ってはいけませんか.m=p−1−−−−√,y=a∗m+bとすると,列挙aとbはブロック列挙に相当する.では、今ではxa∗m+b≡z(modp)がaとbをそれぞれ両側に置くようになりました.xb≡x−a∗mz(modp)左側のxbはせいぜいm個で、hashの中に完全に前処理できることがわかります.

 ll m=ceil(sqrt(p-1));
    ll ni=qsm(x,m);ni=qsm(ni,p-2);//          ，      
    a.clear();
    a[1]=m+1;
    fo(j,1,m-1){
        k=k*x%p;
        if(!a[k])a[k]=j;
    }   

そして右のaを列挙すればいいです.

fo(i,0,m-1){
        ll u=a[y];
        if(u){
            if(u==m+1)printf("%lld
",i*m);
            else printf("%lld
",i*m+u);
            return;
        }
        y=y*ni%p;    
    }
    printf("Orz, I cannot find x!
");

これがO(p√)の空間で時間を取り替える大きなステップアルゴリズムである.優美な暴捜.
推薦テーマ
クラシックな裸の問題SDOI 2011計算機
本人はこんにゃくなので
BSGSアルゴリズムについて知っているのも、これだけしかありません.