当前位置: 首页 > news >正文

学习笔记——BSGS

众所周知,北上广深是中国非常一线的城市,北京是首都,地处……

正片开始!

一、BSGS基础算法

实现目标: A x ≡ B ( m o d P ) , ( gcd ⁡ ( P , A ) = 1 ) A^x\equiv B(\mod P),(\gcd(P,A)=1) AxB(modP),(gcd(P,A)=1)求最小的 x x x
很明显,如果暴力枚举,时间是 O ( P ) O(P) O(P)的,只要题目数据范围大,就死定了。愿意的人欢迎尝试(无100警告)
于是,考虑 ~  莫队
~~~~~~~~~~~~~~~~                 分块
~~~~~~~~~~~~~~~~                 BSGS
为什么我要提前两个?
因为BSGS本质就是分块!
简单讲解一下,就是将本来 P P P种情况,平均分成了$\sqrt p $份,对每份内进行预处理
不直观?好,那就用直观的式子吧!
令 x = k p − t \texttt{令}x=k\sqrt p-t x=kp t
即 A k p ≡ A t B ( m o d p ) \texttt{即}A^{k\sqrt p}\equiv A^tB (\mod p) Akp AtB(modp)

于是,找个哈希表维护一下后面的即可

IO::pin>>y>>z>>p;
gp_hash_table<int,int> ht;
int f,s;
bool flg;
ht.clear();
f=ceil(sqrt(p));
s=1;
flg=1;
for(int i=1; i<=f; i++)s=1ll*s*y%p,ht[1ll*z*s%p]=i;
for(int j=1,k=s; j<=f; j++) {if(ht[k]&&flg) {wt(((1ll*j*f-ht[k])%p+p)%p,'\n');flg=0;}k=(1ll*s*k)%p;}if(flg)puts("Orz, I cannot find x!");

附赠模板代码

#pragma GCC optimize(1,"inline","Ofast")
#pragma GCC optimize(2,"inline","Ofast")
#pragma GCC optimize(3,"inline","Ofast")
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
namespace IO {class input {private:bool isdigit(char c) {return ('0'<=c&&c<='9');}public:input operator>>(int &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(short &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(bool &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(long &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(long long &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(__int128 &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned int &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned short &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned long &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned long long &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned __int128 &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(double &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();if(!y)x=-x;if(!isdigit(c))if(c!='.')return *this;double z=1;while(isdigit(c))z/=10.,x=x+z*(c^48),getchar();return *this;}input operator>>(long double &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();if(!y)x=-x;if(!isdigit(c))if(c!='.')return *this;double z=1;while(isdigit(c))z/=10.,x=x+z*(c^48),c=getchar();return *this;}input operator>>(float &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();if(!y)x=-x;if(!isdigit(c))if(c!='.')return *this;double z=1;while(isdigit(c))z/=10.,x=x+z*(c^48),c=getchar();return *this;}input operator>>(std::string &x) {char c=getchar();x.clear();while(!(c!=' '&&c!='\n'&&c!='	'&&c!=EOF&&c))c=getchar();while(c!=' '&&c!='\n'&&c!='	'&&c!=EOF&&c) {x.push_back(c);c=getchar();}return *this;}input operator>>(char *x) {char c=getchar();int cnt=0;while(!(c!=' '&&c!='\n'&&c!='	'&&c!=EOF&&c))c=getchar();while(c!=' '&&c!='\n'&&c!='	'&&c!=EOF&&c) {x[cnt++]=c;c=getchar();}return *this;}input operator>>(char x) {x=getchar();return *this;}} pin;
};
inline void wt(char ch) {putchar(ch);
}
template<class T>
inline void wt(T x) {static char ch[40];int p=0;if(x<0)putchar('-'),x=-x;doch[++p]=(x%10)^48,x/=10;while(x);while(p)putchar(ch[p--]);
}
template<class T,class... U>
inline void wt(T x,U ...t) {wt(x),wt(t...);
}
#define int long long
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define frep(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define lqrep(i,a,v) for(int i=hd[a],v=e[i].v;i>=i##end;i=e[i].nxt,v=e[i].v)
const int N=1e5+7;
main() {
}
//目前快速输出pout还未搞定哦

到此就结束了吗?

当然不是!!!!!!!!!!

如果没有 gcd ⁡ ( P , A ) = 1 \gcd(P,A)=1 gcd(P,A)=1的话,前面的一切都成了一纸空文
那该如何?
如果不需要的旅客们可以摆烂了,以下是扩展板

二、BSGS基础算法

不妨设 gcd ⁡ ( P , A ) = d \gcd(P,A)=d gcd(P,A)=d
A x ≡ B ( m o d P ) − > ( A ′ × d ) x ≡ B ′ × d ( m o d P ) − > ( A ′ × d ) x − 1 ≡ B ′ ∗ A ′ − 1 ( m o d P ) A^x\equiv B(\mod P)->\\(A'\times d)^x\equiv B'\times d(\mod P)->\\(A'\times d)^{x-1}\equiv B'*A'^{-1}(\mod P) AxB(modP)>(A×d)xB×d(modP)>(A×d)x1BA1(modP)
接着按上文求解即可

相关文章:

学习笔记——BSGS

众所周知&#xff0c;北上广深是中国非常一线的城市&#xff0c;北京是首都&#xff0c;地处…… 正片开始&#xff01; 一、BSGS基础算法 实现目标&#xff1a; A x ≡ B ( m o d P ) , ( gcd ⁡ ( P , A ) 1 ) A^x\equiv B(\mod P),(\gcd(P,A)1) Ax≡B(modP),(gcd(P,A)1)…...

【AI视野·今日NLP 自然语言处理论文速览 第四十期】Mon, 25 Sep 2023

AI视野今日CS.NLP 自然语言处理论文速览 Mon, 25 Sep 2023 Totally 46 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computation and Language Papers ReConcile: Round-Table Conference Improves Reasoning via Consensus among Diverse LLMs Authors Justin C…...

Linux C/C++下收集指定域名的子域名信息(类似dnsmap实现)

我们知道dnsmap是一个工具&#xff0c;主要用于收集指定域名的子域名信息。它对于渗透测试人员在基础结构安全评估的信息收集和枚举阶段非常有用&#xff0c;可以帮助他们发现目标公司的IP网络地址段、域名等信息。 dnsmap的操作原理 dnsmap&#xff08;DNS Mapping&#xff…...

linux-定时任务

目录 一、crond命令 1、什么是计划任务 2、crond服务的概念 3、crontab 二、at命令 1、at任务的概念 三、邮件服务 1、概念 2、启动postfix 四、mailx命令 1、三个概念&#xff1a; 2、交互式发邮件 3、非交互式发邮件 四、cron定时任务实践 1、系统定时任务配置…...

在Spring Boot项目中使用Redisson

在Spring Boot项目中使用Redisson Redisson简介 Redisson官网仓库 Redisson中文文档 Redission是一个基于Java的分布式缓存和分布式任务调度框架&#xff0c;用于处理分布式系统中的缓存和任务队列。它是一个开源项目&#xff0c;旨在简化分布式系统的开发和管理。 以下是…...

JavaScript 函数柯里化

&#x1f3b6;什么是柯里化 柯里化&#xff08;Currying&#xff09;是把接受多个参数的函数变换成接受一个单一参数(最初函数的第一个参数)的函数&#xff0c;并且返回接受余下的参数且返回结果的新函数的技术。 &#x1f3a1;简单的函数柯里化的实现 // ------------- 原函数…...

springboot实现ACL+RBAC权限体系

本文基于web系统的权限控制非常重要的前提下&#xff0c;从ALC和RBAC权限控制两个方面&#xff0c;介绍如何在springboot项目中实现一个完整的权限体系。 源码下载 &#xff1a;https://gitee.com/skyblue0678/springboot-demo 序章 一个后台管理系统&#xff0c;基本都有一套…...

C++20协程示例

C20协程示例 认识协程 在C中&#xff0c;协程就是一个可以暂停和恢复的函数。 包含co_wait、co_yield、co_return关键字的都可以叫协程。 看一个例子&#xff1a; MyCoroGenerator<int> testFunc(int n) {std::cout << "Begin testFunc" << s…...

【Verilog 教程】6.2Verilog任务

关键词&#xff1a;任务 任务与函数的区别 和函数一样&#xff0c;任务&#xff08;task&#xff09;可以用来描述共同的代码段&#xff0c;并在模块内任意位置被调用&#xff0c;让代码更加的直观易读。函数一般用于组合逻辑的各种转换和计算&#xff0c;而任务更像一个过程&a…...

Spring修炼之路(1)基础入门

一、简介 1.1Spring概述 Spring框架是一个轻量级的Java开发框架&#xff0c;它提供了一系列底层容器和基础设施&#xff0c;并可以和大量常用的开源框架无缝集成&#xff0c;可以说是开发Java EE应用程序的必备。Spring是一个轻量级的控制反转(IoC)和面向切面(AOP)的容器&…...

GANs学习记录

GAN 基于GAN的研究识别相关不同背景目标图像 可以用Augmentation2021.3.15 基于GAN的研究 是通过GAN 进行图像重建&#xff0c;恢复细节&#xff0c;去模糊&#xff0c;提高图像质量&#xff0c;图像还原&#xff0c;去噪等等。 识别相关 一种基于生成对抗网络的训练样本扩充…...

Flink-CDC——MySQL、SqlSqlServer、Oracle、达梦等数据库开启日志方法

目录 1. 前言 2. 数据源安装与配置 2.1 MySQL 2.1.1 安装 2.1.2 CDC 配置 2.2 Postgresql 2.2.1 安装 2.2.2 CDC 配置 2.3 Oracle 2.3.1 安装 2.3.2 CDC 配置 2.4 SQLServer 2.4.1 安装 2.4.2 CDC 配置 2.5达梦 2.4.1安装 2.4.2CDC配置 3. 验证 3.1 Flink版…...

linux设置tomcat redis开机自启动

设置Tomcat自启动 1.修改 /etc/rc.d/rc.local 文件 [rootiowZ]# vim /etc/rc.d/rc.local在/etc/rc.d/rc.local文件最后加上&#xff1a; export JAVA_HOME/usr/local/jdk /usr/local/apache-tomcat-8.5.73/bin/startup.sh start退出vim并保存修改的文件。 说明&#xff1a;/u…...

跨域问题讨论

问题 跨域定义 当一个请求url的协议、域名、端口三者之间任意一个与当前页面地址不同即为跨域。 跨域的安全隐患&#xff08;CSRF攻击&#xff09; 也就是说&#xff0c;一旦允许跨域&#xff0c;意味着允许恶意网站随意攻击可信网站&#xff0c;带来安全风险。 这里面有一…...

ESP32设备通信-两个ESP32设备之间HTTP通信

两个ESP32设备之间HTTP通信 文章目录 两个ESP32设备之间HTTP通信1、应用介绍2、软件准备3、硬件准备4、代码实现4.1 ESP32服务器节点代码4.2 ESP32客户端节点代码在本文中,我们将介绍如何在没有任何物理路由器或互联网连接的情况下使用 Wi-Fi 在两个 ESP32 开发板之间执行无线…...

数据结构学习笔记——查找算法中的树形查找(平衡二叉树)

目录 一、平衡二叉树的定义二、平衡因子三、平衡二叉树的插入和构造&#xff08;一&#xff09;LL型旋转&#xff08;二&#xff09;LR型旋转&#xff08;三&#xff09;RR型旋转&#xff08;四&#xff09;RL型旋转 四、平衡二叉树的删除&#xff08;一&#xff09;叶子结点&a…...

P1830 轰炸III

题目背景 一个大小为 &#xfffd;&#xfffd;nm 的城市遭到了 &#xfffd;x 次轰炸&#xff0c;每次都炸了一个每条边都与边界平行的矩形。 题目描述 在轰炸后&#xff0c;有 &#xfffd;y 个关键点&#xff0c;指挥官想知道&#xff0c;它们有没有受到过轰炸&#xff0c;如…...

大语言模型LLM知多少?

你知道哪些流行的大语言模型?你都体验过哪写? GPT-4,Llamma2, T5, BERT 还是 BART? 1.GPT-4 1.1.GPT-4 模型介绍 GPT-4(Generative Pre-trained Transformer 4)是由OpenAI开发的一种大型语言模型。GPT-4是前作GPT系列模型的进一步改进,旨在提高语言理解和生成的能力,…...

Redis命令行使用Lua脚本

Redis命令行使用Lua脚本 Lua脚本在Redis中的使用非常有用&#xff0c;它允许你在Redis服务器上执行自定义脚本&#xff0c;可以用于复杂的数据处理、原子性操作和执行多个Redis命令。以下是Lua脚本在Redis中的基本使用详细讲解&#xff1a; 运行Lua脚本&#xff1a; 在Redis中…...

HTML详细基础(三)表单控件

本帖介绍web开发中非常核心的标签——表格标签。 在日常我们使用到的各种需要输入用户信息的场景——如下图&#xff0c;均是通过表格标签table创造出来的&#xff1a; 目录 一.表格标签 二.表格属性 三.合并单元格 四.无序列表 五.有序列表 六.自定义标签 七.表单域 …...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...