Baby Steps Giant Steps(BSGS)とその拡張——楊子曰アルゴリズム
13920 ワード
Baby Steps Giant Steps(BSGS)とその拡張——楊子曰アルゴリズム
ハイパーリンクハイパーリンク:数学的アセンブリ
別名バス会社、北上広深、抜山蓋世……感嘆:中華漢字は本当に博大で奥深いですね!
BSGS
彼は何ができるんだ?解方程式:a x≡b(m o d p)a^xequiv b(modp)ax≡b(mod p)の最小非負整数解であるが,aとpは互質滴である
まず、不思議な事実をお伝えします.
この方程式に解があれば,最小解は[0,p−1)に違いない.
このことを説明するには、べき乗型のループセクションを引き出す必要があります.
みんなの小学校の时きっと(いいえ、私はしたことがありません)このような问题をしたことがあることを信じます:3 233の位は何ですか?3^{233}のビットは何ですか?3233の席は何ですか.そして、先生が教えてくれます.循環節を探しています.3 1⇒個位は3 3 3 2⇒個位は9 3 3 3⇒個位は7 3 3 4⇒個位は3 3 3 3^1Rightarrow個位は3\3^2Rightarrow個位は93^3Rightarrow個位は7\3^4Rightarrow個位は1\3^5Rightarrow個位は3 31⇒個位は332⇒個位は933⇒個位は734⇒個位135⇒個位3欧、3 5 3^5 35の個位を発見したかどうかは3 1 3^1 31の個位と同じで、これは私が更に下に下がるならば、また39713971で、循環を続けて、4つの循環ごとに1回
それから私たちは233 m o d 4=1 233mod4=1 233 mod 4=1を使って、答え3を得て、それから先生はあなたに1粒の小惑星の小さい星を奨励します
3 x≡b(m o d 10)3^xequivb(mod10)3 x≡b(mod 10)このbの取値は4つしかないことを教えてくれました
では、このことをもう少し拡張して、a x≡b(m o d p)a^xequiv b(modp)ax≡b(mod p)が循環節つまみを生むようにすることはできませんか.--もちろんいいです.理由は簡単です.私たちが見なければならないのは型p以降の値なので、他のものには関心がありません.a xm o d p=a x-1 m o d p
Soは,2回でpが完成した後の値が同じになると,ループ節が生じる.
次に、最終的に解決すべき問題を見てみましょう.a x≡b(m o d p)a^xequiv b(modp)ax≡b(mod p)を解く最小の非負の整数解、aとpの相互作用
左のものは循環節を生み出すので、私たちが得なければならないのもxの最小非負の整数解であれば、循環節で取れる値がbに等しくないことを考慮して、対応するxを出力すればいいのではないでしょうか.
では、次はこのサイクルが最も長くてどのくらいあるかを考えてみましょう.
私たちは2つの方法でこの問題を考えることができます.以前にも述べたように、2つのa x m o d p a^xmodp ax mod pが同じ値を取れば、サイクルセグメントを生成することができますが、1つのデジタル型pの値は最大何種類つまむことができますか?1~p-1(aとpは互いに質が合うため、So,0は取れない)しか取れないが、ハトかごの原理によれば、p個の数は必ず2つの数の取値が同じになる.So,最大p-1個の数は必ず循環節を構成することができ、これは解が[0,p-1](ここでは確かにp-1個の数) にあることを示している.まず:a 0≡1(m o d p)a^0equiv 1(modp)a 0≡1(mod p)、a,p互質のため、更にオーラの定理(あれは何ですか?私を突き刺します)によって得ます:aφ ( p ) ≡ 1 ( m o d p ) a^{\varphi(p)}\equiv 1(\mod\p) aφ(p)≡1(mod p)、つまり0からφ ( p )\varphi(p) φ(p)は必ずループしますが、φ ( p )\varphi(p) φ(p)最大はp-1(pが素数の場合)しか取れず,So,最大はp-1までループ節があるに違いないので,この方程式に解があれば[0,p-1]に必ず を解くことに成功した.
ここまで言うと、0~p-1の暴枚から、とても優秀だと言う人がいるに違いない.
私たちは野蛮人ではありません.効率にこだわって、複雑さをO(p)O(sqrt p)O(p)に下げて、ブロックのような考えを使います(それは何ですか、スタンプ)
命令t=⌈p⌉t=leftlceilsqrt prightrceil t=⌈p⌉
x=i∗t−j x=i*t−j x=i∗t−jとすると、iは[0,t]にあり、jは[0,t)の中で、このように必ずすべての状況をカバーすることができて、それでは方程式は:a i∗t−j≡b(m o d p)a^{i*t−j}equiv b(modp)ai∗t−j≡b(mod p)そこでこのようになりました:(a t)i≡b∗a j(m o d p)(a^t)^iequiv b*a^j(modp)(at)i≡b∗aj(mod)そして右側の値は⌈p⌉leftlceilsqrt prightrceil⌈p⌉種だけで、左の値も⌈p⌉leftlceilsqrt prightrceil⌈p⌉種だけで、私たちは美しくマッチすることができます
まずjを列挙して、右のすべての情況を1つのhashの中に投げて(私達はこれを管理してBaby Step sと言います)、それからiを列挙して、左の値を算出して、hashの表の中であるかどうかを探して(私達はこれを管理してGiant Step sと言います)、終わります!
stl大法がよい
拡張BSGS
つまり問題はaとpが互いに質を持たないことになって、それではどのようにつまむことをしますか?
じゃあaとpを互質にすれば終わりじゃないの?
d=gcd(a,p)d=gcd(a,p)d=gcd(a,p)式全体をd(この過程でdがbを完全に除去しなければb=1でない限り解はない)を除去し,得られた:a x d≡b d(m o d p d)frac{a^x}{d}equivfrac{ b}{d}(mod\frac{ p}{d})dax≡db(mod dp)一つのa x−1 a^{x−1}ax−1}ax−1を持ち出した:a x−1∗a d≡b d(m o d p d)a^{x−1}*frac{ a}{d}equivfrac{ b}(modfrac{ b}{d}(modfrcfrac{ b}{d}(modfrdfrac{ d}ac{p}{d})ax−1∗da≡db(mod dp)
今想像してみてください.もし私たちがこのa dfrac{a}{d}daを等号の右側に除けば(プログラムではここで項目を移さないでください)、方程式は元のフォーマットに戻りますか?
元のa x a^x axはa x−1 a^{x−1}ax−1になり,pはp dfrac{p}{d}dpになった
a x−1 a^{x−1}ax−1とp dfrac{p}{d}dpも必ずしも互質ではないと言う人もいるに違いない.
大丈夫です.dが1になるまで上記の操作を繰り返します.では、最もこの方程式はこうなります.a x−k∗a k∏d i≡b∏d i(m o d p∏d i)a^{x−k}*frac{a^k}{prod d_i}equivfrac{b}{prod_i}(mod\frac{p}{prod_i})ax−k∗∏di b(mod∏dip)
今、私たちはa k∏d ifrac{a^k}{prod_i}∏di akを移動します(ここでは逆元を使います.できない子供靴で私を突き刺します)
方程式は元のフォーマットで、しかもこの時a x−k a^{x−k}ax−kとp∏d ifrac{p}{prod d d_i}∏dipはきっと互いに質を交換したに違いない.
そして私たちはBSGSを美しく使うことができます(この時求めたのはx-kで、答えはkを加えることを忘れないでください)!
しかし、その前に、答えが0~kの場合、kはlog級で、暴力は大丈夫ですが、この部分はgcdを除いたついでに作ることができます.
OK
参照先:https://www.cnblogs.com/sdzwyq/p/9900650.html『アルゴリズムコンテスト進級ガイド』李煜東著
HG機械室で
ハイパーリンクハイパーリンク:数学的アセンブリ
別名バス会社、北上広深、抜山蓋世……感嘆:中華漢字は本当に博大で奥深いですね!
BSGS
彼は何ができるんだ?解方程式:a x≡b(m o d p)a^xequiv b(modp)ax≡b(mod p)の最小非負整数解であるが,aとpは互質滴である
まず、不思議な事実をお伝えします.
この方程式に解があれば,最小解は[0,p−1)に違いない.
このことを説明するには、べき乗型のループセクションを引き出す必要があります.
みんなの小学校の时きっと(いいえ、私はしたことがありません)このような问题をしたことがあることを信じます:3 233の位は何ですか?3^{233}のビットは何ですか?3233の席は何ですか.そして、先生が教えてくれます.循環節を探しています.3 1⇒個位は3 3 3 2⇒個位は9 3 3 3⇒個位は7 3 3 4⇒個位は3 3 3 3^1Rightarrow個位は3\3^2Rightarrow個位は93^3Rightarrow個位は7\3^4Rightarrow個位は1\3^5Rightarrow個位は3 31⇒個位は332⇒個位は933⇒個位は734⇒個位135⇒個位3欧、3 5 3^5 35の個位を発見したかどうかは3 1 3^1 31の個位と同じで、これは私が更に下に下がるならば、また39713971で、循環を続けて、4つの循環ごとに1回
それから私たちは233 m o d 4=1 233mod4=1 233 mod 4=1を使って、答え3を得て、それから先生はあなたに1粒の小惑星の小さい星を奨励します
3 x≡b(m o d 10)3^xequivb(mod10)3 x≡b(mod 10)このbの取値は4つしかないことを教えてくれました
では、このことをもう少し拡張して、a x≡b(m o d p)a^xequiv b(modp)ax≡b(mod p)が循環節つまみを生むようにすることはできませんか.--もちろんいいです.理由は簡単です.私たちが見なければならないのは型p以降の値なので、他のものには関心がありません.a xm o d p=a x-1 m o d p
Soは,2回でpが完成した後の値が同じになると,ループ節が生じる.
次に、最終的に解決すべき問題を見てみましょう.a x≡b(m o d p)a^xequiv b(modp)ax≡b(mod p)を解く最小の非負の整数解、aとpの相互作用
左のものは循環節を生み出すので、私たちが得なければならないのもxの最小非負の整数解であれば、循環節で取れる値がbに等しくないことを考慮して、対応するxを出力すればいいのではないでしょうか.
では、次はこのサイクルが最も長くてどのくらいあるかを考えてみましょう.
私たちは2つの方法でこの問題を考えることができます.
ここまで言うと、0~p-1の暴枚から、とても優秀だと言う人がいるに違いない.
私たちは野蛮人ではありません.効率にこだわって、複雑さをO(p)O(sqrt p)O(p)に下げて、ブロックのような考えを使います(それは何ですか、スタンプ)
命令t=⌈p⌉t=leftlceilsqrt prightrceil t=⌈p⌉
x=i∗t−j x=i*t−j x=i∗t−jとすると、iは[0,t]にあり、jは[0,t)の中で、このように必ずすべての状況をカバーすることができて、それでは方程式は:a i∗t−j≡b(m o d p)a^{i*t−j}equiv b(modp)ai∗t−j≡b(mod p)そこでこのようになりました:(a t)i≡b∗a j(m o d p)(a^t)^iequiv b*a^j(modp)(at)i≡b∗aj(mod)そして右側の値は⌈p⌉leftlceilsqrt prightrceil⌈p⌉種だけで、左の値も⌈p⌉leftlceilsqrt prightrceil⌈p⌉種だけで、私たちは美しくマッチすることができます
まずjを列挙して、右のすべての情況を1つのhashの中に投げて(私達はこれを管理してBaby Step sと言います)、それからiを列挙して、左の値を算出して、hashの表の中であるかどうかを探して(私達はこれを管理してGiant Step sと言います)、終わります!
stl大法がよい
ll bsgs(ll a,ll b,ll p){//return -1
if (b>=p) return -1;
map<ll,ll> mp;
mp.clear();
b%=p;
ll t=(ll)sqrt(p)+1;
for (ll j=0;j<t;j++){
ll v=b*pow(a,j,p)%p;
mp[v]=j;
}
a=pow(a,t,p);
if (a==0){
if (b==0) return 1;
else return -1;
}
for (ll i=0;i<=t;i++){
ll v=pow(a,i,p);
if (mp.find(v)!=mp.end()){
ll tmp=mp[v];
if (i*t-tmp>=0) return i*t-tmp;
}
}
return -1;
}
拡張BSGS
つまり問題はaとpが互いに質を持たないことになって、それではどのようにつまむことをしますか?
じゃあaとpを互質にすれば終わりじゃないの?
d=gcd(a,p)d=gcd(a,p)d=gcd(a,p)式全体をd(この過程でdがbを完全に除去しなければb=1でない限り解はない)を除去し,得られた:a x d≡b d(m o d p d)frac{a^x}{d}equivfrac{ b}{d}(mod\frac{ p}{d})dax≡db(mod dp)一つのa x−1 a^{x−1}ax−1}ax−1を持ち出した:a x−1∗a d≡b d(m o d p d)a^{x−1}*frac{ a}{d}equivfrac{ b}(modfrac{ b}{d}(modfrcfrac{ b}{d}(modfrdfrac{ d}ac{p}{d})ax−1∗da≡db(mod dp)
今想像してみてください.もし私たちがこのa dfrac{a}{d}daを等号の右側に除けば(プログラムではここで項目を移さないでください)、方程式は元のフォーマットに戻りますか?
元のa x a^x axはa x−1 a^{x−1}ax−1になり,pはp dfrac{p}{d}dpになった
a x−1 a^{x−1}ax−1とp dfrac{p}{d}dpも必ずしも互質ではないと言う人もいるに違いない.
大丈夫です.dが1になるまで上記の操作を繰り返します.では、最もこの方程式はこうなります.a x−k∗a k∏d i≡b∏d i(m o d p∏d i)a^{x−k}*frac{a^k}{prod d_i}equivfrac{b}{prod_i}(mod\frac{p}{prod_i})ax−k∗∏di b(mod∏dip)
今、私たちはa k∏d ifrac{a^k}{prod_i}∏di akを移動します(ここでは逆元を使います.できない子供靴で私を突き刺します)
方程式は元のフォーマットで、しかもこの時a x−k a^{x−k}ax−kとp∏d ifrac{p}{prod d d_i}∏dipはきっと互いに質を交換したに違いない.
そして私たちはBSGSを美しく使うことができます(この時求めたのはx-kで、答えはkを加えることを忘れないでください)!
しかし、その前に、答えが0~kの場合、kはlog級で、暴力は大丈夫ですが、この部分はgcdを除いたついでに作ることができます.
OK
ll ex_bsgs(ll a,ll b,ll p){
if (b==1) return 0;
ll d=gcd(a,p),k=0,s=1;
while(d>1){
if (b%d!=0) return -1;
k++;
b/=d;
p/=d;
s=(s*a/d)%p;
if (s==b) return k;
d=gcd(a,p);
}
ll x,y;
ex_gcd(s,p,x,y);
b=(b*x%p+p)%p;
ll tmp=bsgs(a,b,p);
if (tmp==-1) return -1;
else return tmp+k;
}
参照先:https://www.cnblogs.com/sdzwyq/p/9900650.html『アルゴリズムコンテスト進級ガイド』李煜東著
HG機械室で