BSGS

男娘i 2021-12-15 06:39 197阅读 0赞

**BSGS**  
  
用途：给定形如$A^x \\equiv z (mod  p)$(p为质数)的式子，给定A、z、p,求满足条件的x的最小值。

解法：

考虑暴力，暴力枚举0到p-1并验证，复杂度O(n)。

考虑优化：考虑通过预处理来加速算法。

$$A^x \\equiv z (mod  p)$$

设$c$=$\\sqrt\{p\}$，也就是我们的块大小，

$$A^\{ic+j\} \\equiv z (mod  p)$$

$$A^j \\equiv z\*A^\{-ic\} (mod  p)$$

我们把$1$到$c$的$A^i$存入hash池中，这样我们每次枚举$A^\{-ic\}\*z$,在hash池中查询，这样就可以同时检验$1--c$个值是否出现。

具体来说就是如果查询到一个值，设其为T,则

$$A^T \\equiv z\*A^\{-ic\} (mod  p)$$

x为T+ic。

复杂度O($\\sqrt\{n\}$)。

优化的地方在于我们一次可以同时比较$\\sqrt\{n\}$个值。

--------------------

**拓展BSGS：**

$$A^x \\equiv z (mod  p)$$

同时两边取t=gcd(A,P)。

原式 ：

$$A^\{x-1\}\*\\frac\{A\}\{t\} \* t \\equiv \\frac\{z\}\{t\} \* t (mod  \\frac\{p\}\{t\} \* t)$$

则，现在原式变成：

$$ A^\{x-1\}\*\\frac\{A\}\{t\} \\equiv \\frac\{z\}\{t\} (mod  \*\\frac\{p\}\{t\})$$

这个过程会一直进行直到A、P互质。

显然，当z在中途无法被除尽时，就是无解。

现在，原式变成：

$$ A^\{x-k\}\*C \\equiv T (mod  P)$$

由于$C$是由若干个A除若干个其他因子得到，$C$与$P$必然也互质。

用欧拉定理把$C$的逆元乘到右边，然后再用普通BSGS即可。

注意最后算答案的时候$A$是减了$K$个的，我们把$K$加上就行。

转载于:https://www.cnblogs.com/wuzewen/p/11121249.html

发表评论取消回复

表情：

评论列表（有 0 条评论，197人围观）

还没有评论，来说两句吧...

相关阅读

相关 Uva1191————思维+bsgs算法

可以看这篇博客][Link 1] include<bits/stdc++.h> define ll long long using namesp...

青旅半醒/ 2024年04月18日 23:25/ 0 赞/ 44 阅读

相关 BSG白山极客挑战赛 B君的圆锥

[B君的圆锥][B] ![male.jpg][] [wwwwodddd][] (命题人) 基准时间限制：1 秒空间限制：131072 KB 分值: 40 B君要用一个

心已赠人/ 2022年08月22日 14:16/ 0 赞/ 127 阅读

相关大步小步算法 (BSGS算法)

大步小步算法是专门用来求解a^x = b(mod n)这种方程的，这种问题也称为离散对数问题。已知a，b，n，且n为素数，求x。模板如下 include <i

水深无声/ 2022年06月12日 03:37/ 0 赞/ 137 阅读

相关 BZOJ2242[SDOI2011]计算器——exgcd+BSGS

题目描述你被要求设计一个计算器完成以下三项任务： 1、给定y,z,p,计算Y^Z Mod P 的值； 2、给定y,z,p，计算满足xy≡ Z ( mod P )的最

约定不等于承诺〃/ 2022年01月05日 15:15/ 0 赞/ 219 阅读

相关 BSGS与exBSGS学习笔记

\\(BSGS\\)用于解决这样一类问题： > 求解\\(A^x ≡B(modP)\\)的最小\\(x\\)，其中\\(P\\)为质数。这里我们采用分块的方法，把\\(x

短命女/ 2022年01月05日 15:05/ 0 赞/ 186 阅读

相关 BSGS

BSGS 用途：给定形如$A^x \\equiv z (mod p)$(p为质数)的式子，给定A、z、p,求满足条件的x的最小值。解法：考虑暴力

男娘i/ 2021年12月15日 06:39/ 0 赞/ 197 阅读

相关 uva 11916 Emoogle Grid （BSGS）

[UVA 11916][] 　　BSGS的一道简单题，不过中间卡了一下没有及时取模，其他这里的100000007是素数，所以不用加上拓展就能做了。代码如下： ![Con

ゞ浴缸里的玫瑰/ 2021年12月14日 12:43/ 0 赞/ 171 阅读

相关 bzoj5104 Fib数列（BSGS+二次剩余）

快AFO了才第一次写二次剩余的题…… 显然应该将Fn写成通项公式（具体是什么写起来不方便而且大家也都知道），设t=((1+√5)/2)n,T=√5N，然后可以得到t-(-1)

向右看齐/ 2021年11月01日 08:44/ 0 赞/ 204 阅读

相关 2019牛客暑期多校训练营（第五场）C - generator 2 (BSGS)

[题目链接][Link 1] 题意：给定\\(n,x\_0,a,b,p\\)，有递推式\\(x\_i = (a \\cdot x\_\{i-1\} +b)\\%p

我不是女神ヾ/ 2021年10月29日 07:48/ 0 赞/ 241 阅读

相关模板—BSGS

include<iostream> include<cstdio> include<cmath> include<map> define

你的名字/ 2021年10月29日 07:18/ 0 赞/ 184 阅读