首页 > 其他分享 >BSGS 学习笔记

BSGS 学习笔记

时间:2024-07-25 21:28:28浏览次数:11  
标签:return dfrac ll 笔记 学习 ans sum BSGS

BSGS

拔山盖世、北上广深……

实际上叫大步小步,用于解决高次同余方程,形如:

\[a^x\equiv b\pmod p \]

求 \(x\)。

设 \(x=i\times t-j\),有:

\[a^{i\times t-j}\equiv b\pmod p \]

\[a^{i\times t}\equiv b\times a^j\pmod p \]

预处理每个 \(j\),枚举 \(i\) 处理,\(t\) 取 \(\sqrt n\) 最优,复杂度为 \(O(\sqrt n)\)。

点击查看代码
ll BSGS(ll a,ll b,ll P)
{
    if(1%p==b%p) return 0;//特判。
    unordered_map<int,int>vis;
    b%=P;
    ll t=sqrt(P)+1,sum=b;
    for(int i=0;i<=t-1;i++) 
    {
        vis[sum]=i;
        (sum*=a)%=P;
    }
    a=qpow(a,t,P);
    if(!a) return b==0?1:-1;
    sum=1;
    for(int i=1;i<=t;i++)
    {
        (sum*=a)%=P;
        if(vis.find(sum)!=vis.end()&&i*t-vis[sum]>=0)
            return i*t-vis[sum];
    }
    return -1;
}

例题

P3846 [TJOI2007] 可爱的质数/【模板】BSGS

板子。

P4884 多少个 1?

\(\sum\limits_{i=0}^{n-1}10^i\equiv b\pmod p\) 等价于 \(10^n\equiv b\times 9+1\pmod P\)。

P4454 [CQOI2018] 破解D-H协议

原根的性质是为了表示 \(a,p\) 互质的,之后直接跑 BSGS 即可。

P3306 [SDOI2013] 随机数生成器

当 \(a=0\) 的时候直接判掉就好了。

先忽略模数,若 \(a\ne 1\),推式子有:

\[\begin{aligned} x_n&=ax_{n-1}+b \\ &=a^2x_{n-2}+(a+1)b\\ &=a^{n-1}x_1+(a^{n-2}+a^{n-1}+…+a_0)b \end{aligned} \]

右面是一个等比数列,套求和公式 \(s_{n}=\dfrac{x_1(a^n-1)}{a-1}\)。

\[\begin{aligned} x_n&=a^{n-1}x_1+\dfrac{b(a^{n-1}-1)}{a-1}\\ &=a^{n-1}(x_1+\dfrac{b}{a-1})-\dfrac{b}{a-1}\\ \end{aligned} \]

故此有 \(a^{n-1}(x_1+\dfrac{b}{a-1})\equiv x_n+\dfrac{b}{a-1}\pmod p\)

需满足 \(a,p\) 互质,发现 \(p\) 为质数,\(\gcd(a,p)\) 只可能等于 \(1\) 或 \(p\),若等于 \(1\) 不用管,等于 \(p\) 显然无解了,然后跑 \(BSGS\) 即可。

\(a=1\) 的特殊处理即可。

点击查看代码
#include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
ll T,p,a,b,x,t;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll b,ll P)
{
    ll ans=1;
    for(;b;b>>=1)
    {
        if(b&1) (ans*=a)%=P;
        (a*=a)%=P;
    }
    return ans;
}
ll BSGS(ll a,ll b,ll P)
{
    if(1%P==b%P) return 0;
    unordered_map<ll,ll>vis;
    b%=P;
    ll t=sqrtl(P)+1,sum=b;
    for(int i=0;i<=t-1;i++)
    {
        vis[sum]=i;
        (sum*=a)%=P;
    }
    a=qpow(a,t,P);
    if(!a) return b==0?1:-1;
    sum=1;
    for(int i=0;i<=t;i++)
    {
        if(vis.find(sum)!=vis.end()&&i*t-vis[sum]>=0)
            return i*t-vis[sum];
        (sum*=a)%=P;
    }
    return -1;
}
signed main()
{
    read(T);
    while(T--)
    {
        read(p),read(a),read(b),read(x),read(t);
        if(x==t) {puts("1"); continue;}
        if(a==0)
        {
            if(t==b) puts("2");
            else puts("-1");
        }
        else if(a==1)
        {
            ll g=gcd(b,p);
            if(g==p) puts("-1");
            else
            {
                ll ans=((t-x+p)%p)*qpow(b,p-2,p)%p;
                write(ans+1),puts("");
            } 
        }
        else 
        {
            ll c=b*qpow(a-1,p-2,p)%p;
            ll g=gcd(x+c,p);
            if(g==p) puts("-1");
            else 
            {
                ll ans=BSGS(a,(t+c)%p*qpow(x+c,p-2,p)%p,p);
                write(ans==-1?-1:ans+1),puts("");
            }
        }
    }
}

BZOJ4128 Matrix

矩阵乘法 + BSGS。

点击查看代码
#include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=75;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
ll n,P,a[N][N],b[N][N];
struct aa 
{
    ll x[N][N];
    aa() {memset(x,0,sizeof(x));}
    bool operator < (aa another) const
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(x[i][j]<another.x[i][j]) return 1;
                if(x[i][j]>another.x[i][j]) return 0;
            }
        return 0;
    }
};
aa mul(aa a,aa b,ll P)
{
    aa c;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                (c.x[i][j]+=(a.x[i][k]*b.x[k][j])%P)%=P;
    return c;
}
aa qpow(aa a,ll b,ll P)
{
    aa ans;
    for(int i=1;i<=n;i++) ans.x[i][i]=1;
    for(;b;b>>=1)
    {
        if(b&1) ans=mul(ans,a,P);
        a=mul(a,a,P);
    }
    return ans;
}
ll BSGS(aa a,aa b,ll P)
{
    map<aa,ll>vis;
    ll t=sqrt(P)+1;
    for(int i=0;i<=t-1;i++)
    {
        vis[b]=i;
        b=mul(b,a,P);
    }
    a=qpow(a,t,P);
    aa sum;
    for(int i=1;i<=n;i++) sum.x[i][i]=1;
    for(int i=0;i<=t;i++)
    {
        if(vis.find(sum)!=vis.end()&&i*t-vis[sum]>=0)
            return i*t-vis[sum];
        sum=mul(sum,a,P);
    }
    return -1;
}
signed main()
{
    read(n),read(P);
    aa a,b;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            read(a.x[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            read(b.x[i][j]);
    write(BSGS(a,b,P));
}

exBSGS

当 \(a,p\) 不互质的时候,可以不断除去 \(\gcd(a,p)\),直至其互质,依据 \(a\equiv b\pmod p\) 等价于 \(\dfrac{a}{d}\equiv \dfrac{b}{d}\pmod {\dfrac{p}{d}}\)。

设 \(d_i\) 表示直至 \(a,p\) 互质前第 \(i\) 个 \(\gcd(a,p)\),总共进行 \(t\) 次,最后有:

\[a^{x-t}\times \dfrac{a^t}{\prod\limits_{i=1}^td_i}\equiv \dfrac{b}{\prod\limits_{i=1}^td_i}\pmod {\dfrac{p}{\prod\limits_{i=1}^td_i}} \]

之后直接跑 BSGS 即可,中间过程中一旦出现 \(b\) 无法被 \(d_i\) 整除则无解。

发现最后 \(p\) 不一定为质数,所以用 exgcd 求逆元。

点击查看代码
ll BSGS(ll a,ll b,ll P)
{
    if(1%P==b%P) return 0;
    unordered_map<ll,ll>vis;
    b%=P;
    ll t=sqrt(P)+1,sum=b;
    for(int i=0;i<=t-1;i++) 
    {
        vis[sum]=i;
        (sum*=a)%=P;
    }
    a=qpow(a,t,P);
    if(!a) return b==0?1:-1;
    sum=1;
    for(int i=0;i<=t;i++)
    {
        if(vis.find(sum)!=vis.end()&&i*t-vis[sum]>=0)
            return i*t-vis[sum];
        (sum*=a)%=P;
    }
    return -1;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0) {x=1,y=0; return a;}
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
ll inv(ll a,ll P)
{
    ll x,y;
    exgcd(a,P,x,y);
    x=(x%P+P)%P;
    return x;
}
ll exBSGS(ll a,ll b,ll P)
{
    if(b==1||P==1) return 0;
    ll d=gcd(a,P),k=0,mul=1;
    while(d!=1)
    {
        if(b%d!=0) return -1;
        k++;
        b/=d,P/=d;
        mul=mul*(a/d)%P;
        if(mul==b) return k;
        d=gcd(a,P);
    }
    ll ans=BSGS(a,b*inv(mul,P)%P,P);
    if(ans==-1) return -1;
    return ans+k;
}

例题

P4195 【模板】扩展 BSGS/exBSGS

板子。

标签:return,dfrac,ll,笔记,学习,ans,sum,BSGS
From: https://www.cnblogs.com/Charlieljk/p/18324177

相关文章

  • 7月24日JavaSE学习笔记
    序列化版本控制序列化:将内存对象转换成序列(流)的过程反序列化:将对象序列读入程序,转换成对象的方式;反序列化的对象是一个新的对象。serialVersionUID是一个类的序列化版本号privatestaticfinallongserialVersionUID=1L;//版本号如果序列化版本号没有定义,JDK会自动......
  • 7月25日JavaSE学习笔记
    线程的生命周期中,等待是主动的,阻塞是被动的锁对象创建锁对象,锁对象同一时间只允许一个线程进入//创建锁对象Locklock=newReentrantLock(true);//创建可重入锁可重入锁:在嵌套代码块中,锁对象一样就可以直接进入执行公平锁:保证线程获取锁的顺序与线程请求锁的顺序......
  • 嵌入式学习第三天:转义字符、算术运算、类型转换...
    目录转义字符运算符优先级和结合性+加法运算符 -减法运算符*乘法运算符/除法运算符%求余运算符/的注意要点: %的注意要点:--自减运算符++自增运算符&取地址运算符,逗号运算符=赋值运算符不同类型的数据间混合赋值总结高精度——>低精度长类型——>短......
  • Django学习(一)
    Django起源:项目创建:项目执行(测试开发阶段): 项目结束: 结构:db.sqlite3:数据库,一般不用,会替换成我们自己的数据库manage.py 项目同名目录: settings.py settings中的配置详解:   注意:添加自定义配置时名称必须大写 django处理url的过程 视图函数 ......
  • 文本笔记
    1.画盒子大盒子dvi,小盒子p 2.类选择器. id选择器#文本属性::text-align居中属性tetx-aligin本质是控制内容剧中的,属性设置给内容设置文本属性:text-indent:2em;font-size:文本大小30px;文本修饰线:text-decoration:none;去掉线underlines下划线line-throug......
  • Java笔记day10
    一,不同方式创建多个线程并打印(1)定义了一个RunA实现Runnable接口,定义list存储数据,并重写了run方法 ,在run方法里定义循环向list中添加数据a;在main方法中创建a,b两个线程并引用该run方法,输出run对象的list和长度publicstaticvoidmainB(String[]args){RunAru......
  • 前段学习笔记
    <form>表单一般包含按钮<input>标签使用:登录,注册,搜索typetest文本,password密码,rodio单选,checkbox多选,file文件上传表格<table用来展示数据>table代表盒子,tr是行,th是表头单元格,td是内容单元格table无边框,加border属性添加边框。th有加粗和居中的效果普通在td里面......
  • 深度学习与图像识别学习笔记day1
    文件不可以与现有的包重名哦1、Theano(旧)一个python库,可用于定义、优化与计算数学表达式,特别是多维数组(numpy.ndarray),可以理解为一个数学表达式的编译器:用符号式语言定义程序员所需的结果,并可以高效的运行与GPU与CPU上。2、Tensorflow(新)基于计算图实现自动微分系统,tensorflow......
  • 嵌入式学习第9天——C语言运算符,程序设计结构,输入输出缓冲机制
    2024.7.25第九天笔记关于++混合操作,不同计算结果推理第一种编译结果:inti=5;intsum=(++i)+(++i)=6+7=13第二种编译结果:inti=5;intsum=(++i)+(++i)=6+7=7+7前面的7是因为后面i的变化被影响后,重新赋值=14第一种编译结果:inti=5;in......
  • Day10--mybatis多表连接查询学习(一对一、一对多、多对多)
    MyBatis是一个优秀的持久层框架,支持将SQL语句、存储过程以及高级映射转换成Java对象。下面是MyBatis处理一对一、一对多、多对多关系的方式及相应的代码示例。数据库表假设有四个表:user、orders、role、user_role---->创建代码(占位较长)放在文章末尾···首先先了解对应......