首页
登录 | 注册

BSGS算法

BSGS算法

我是看着\(ppl\)的博客学的,您可以先访问\(ppl\)的博客

Part1 BSGS算法

求解关于\(x\)的方程
\[y^x=z(mod\ p)\]

其中\((y,p)=1\)
做法并不难,我们把\(x\)写成一个\(am-b\)的形式
那么,原式变成了
\(y^{am}=zy^b(mod\ p)\)
我们求出所有\(b\)可能的取值(0~m-1),并且计算右边的值
同时用哈希或者\(map\)之类的东西存起来,方便查询
对于左边,我们可以枚举所有可能的\(a\),然后直接查右边的值有没有相等的即可
复杂度是\(O(max(m,p/m))\)
不难证明\(m=\sqrt(p)\)时复杂度最优

所以\(bsgs\)算法的复杂度是\(O(\sqrt(p))\)

模板题:\(SDOI2011\) 计算器

关键代码:

int m=sqrt(p)+1;Hash.Clear();
for(RG int i=0,t=z;i<m;++i,t=1ll*t*y%p)Hash.Insert(t,i);
for(RG int i=1,tt=fpow(y,m,p),t=tt;i<=m+1;++i,t=1ll*t*tt%p)
{
    int k=Hash.Query(t);if(k==-1)continue;
    printf("%d\n",i*m-k);return;
}

使用\(map\)会多个\(log\),在洛谷上我写的\(Hash\)目前是跑得最快的。。。

Part2 拓展BSGS

假设\(gcd(y,p)\neq 1\)怎么办?
\(d=gcd(y,p)\)
将方程改写成等式形式
\[y^x+kp=z\]
发现此时的\(z\)必须要是\(d\)的倍数,否则无解。
因此,除掉\(d\)
\[\frac{y}{d}y^{x-1}+k\frac{p}{d}=\frac{z}{d}\]
这样前面的\(y/d\)就是一个系数了,
不断检查\(gcd(\frac{z}{d},y)\),一直除到互质为止
此时的形式就变成了
\[\frac{y^k}{d}y^{x-k}=\frac{z}{d}(mod\ \frac{p}{d})\]
这样子\(bsgs\)求解之后在还原回去就行了。

模板:SPOJ Power Modulo Inverted
关键代码

void ex_BSGS(int y,int z,int p)
{
    if(z==1){puts("0");return;}
    int k=0,a=1;
    while(233)
    {
        int d=__gcd(y,p);if(d==1)break;
        if(z%d){NoAnswer();return;}
        z/=d;p/=d;++k;a=1ll*a*y/d%p;
        if(z==a){printf("%d\n",k);return;}
    }
    Hash.clear();
    int m=sqrt(p)+1;
    for(int i=0,t=z;i<m;++i,t=1ll*t*y%p)Hash.Insert(t,i);
    for(int i=1,tt=fpow(y,m,p),t=1ll*a*tt%p;i<=m;++i,t=1ll*t*tt%p)
    {
        int B=Hash.Query(t);if(B==-1)continue;
        printf("%d\n",i*m-B+k);return;
    }
    NoAnswer();
}

相关文章

  • 算法推导过程参见[dijkstra算法推导详解] 此文为[dijkstra算法代码实现] https://www.cnblogs.com/Halburt/p/10767389.html package a; import java.util ...
  • 快三个月没写博客了,一直在忙着准备面试和去面试的路上,所以没时间写,也没什么想写的.现在告一段落,就总结一波! 面经 本人真的是双非一本.为什么加“真的”?因为有的人也写着"双非一本,进入阿里",但是某电子科技大学,比9 ...
  • 一.前言 在日常开发中,我们经常会碰到需要在运行时才知道对象个数的情况,这种情况不能使用数组,因为数组是固定数量的,这个时候我们就会使用集合,因为集合可以存储数量不确定的对象. 集合类是特别有用的工具类,不仅可以存储数量不等的对象,还可以实 ...
  • 机器学习web服务化实战:一次吐血的服务化之路
    背景 在公司内部,我负责帮助研究院的小伙伴搭建机器学习web服务,研究院的小伙伴提供一个机器学习本地接口,我负责提供一个对外服务的HTTP接口. 说起人工智能和机器学习,python是最擅长的,其以开发速度快,第三方库多而广受欢迎,以至于现 ...
  • 已经更新100+篇~ 关注公众号,BAT大神带你飞~ 听说你还在写Java,看Spring,看Dubbo,今天SpringCloud, 明天Dubbo3.X新版本... 10个开发9个半在写Java后台?框架层出不穷,天天学新东西怕被甩淘汰 ...
  • More Effective C++
    More Effective C++ 35个改善编程与设计的有效方法 只有深入了解C++编译器如何解释代码, 才有可能用C++语言写出健壮的软件. C++的难学, 不仅在其广博的语法, 语法背后的语义, 语义背后的深层思维, 深层思维背后的 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.073 s.
京ICP备10005923号