AcWing算法提高课-5.6.1同余方程
宣传一下 算法提高课整理
CSDN个人主页:更好的阅读体验

原题链接
题目描述
求关于 x x x 的同余方程 a x ≡ 1 ( m o d b ) ax ≡ 1 \pmod b ax≡1(modb) 的最小正整数解。
输入格式
输入只有一行,包含两个正整数 a , b a,b a,b,用一个空格隔开。
输出格式
输出只有一行,包含一个正整数 x x x,表示最小正整数解。
输入数据保证一定有解。
数据范围
2 ≤ a , b ≤ 2 × 1 0 9 2 \le a,b \le 2 \times 10^9 2≤a,b≤2×109
输入样例:
3 10
输出样例:
7
思路
我们对 a x ≡ 1 ( m o d b ) ax ≡ 1 \pmod b ax≡1(modb) 进行变形:
设 y ∈ R y \in \mathbb{R} y∈R,则:
a x ≡ 1 ( m o d b ) ⇔ a x − b y = 1 ax \equiv1 \pmod b \Leftrightarrow ax-by=1 ax≡1(modb)⇔ax−by=1
我们知道,扩展欧几里得算法可以计算形如 a x + b y = gcd ( a , b ) ax+by=\gcd(a,b) ax+by=gcd(a,b) 的方程的解。
所以直接进行转化即可。
注意: 由于题目要求输出正整数解,所以我们输出 ( x m o d p + p ) m o d p (x \bmod p + p) \bmod p (xmodp+p)modp 即可。
算法时间复杂度 O ( log n ) O(\log n) O(logn)
AC Code
C + + \text{C}++ C++
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;LL exgcd(LL a, LL b, LL &x, LL &y)
{if (!b){x = 1, y = 0;return a;}LL d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}int main()
{LL a, b, x, y;cin >> a >> b;exgcd(a, b, x, y);cout << (x % b + b) % b << endl;return 0;
}

最后,如果觉得对您有帮助的话,点个赞再走吧!
相关文章:
AcWing算法提高课-5.6.1同余方程
宣传一下 算法提高课整理 CSDN个人主页:更好的阅读体验 原题链接 题目描述 求关于 x x x 的同余方程 a x ≡ 1 ( m o d b ) ax ≡ 1 \pmod b ax≡1(modb) 的最小正整数解。 输入格式 输入只有一行,包含两个正整数 a , b a,b a,b,用一…...
Docker Tutorial
什么是Docker 为每个应用提供完全隔离的运行环境 Dockerfile, Image,Container Image: 相当于虚拟机的快照(snapshot)里面包含了我们需要部署的应用程序以及替它所关联的所有库。通过image,我们可以创建很…...
平面图—简单应用
平面图:若一个图𝐺能画在平面𝑆上,且使𝐺的边仅在端点处相交,则称图𝐺为可嵌入平面𝑆,𝐺称为可平面图,简称为平面图。 欧拉公式:设有…...
安装JDK(Java SE Development Kit)超详细教程
文章时间 : 2023-10-04 1. 下载地址 直接去下载地址:https://www.oracle.com/java/technologies/downloads/ (需要翻墙,不想翻墙或者不想注册oracel账号的,直接去我的阿里云盘) 阿里云盘:http…...
KUKA机器人通过3点法设置工作台基坐标系的具体方法
KUKA机器人通过3点法设置工作台基坐标系的具体方法 具体方法和步骤可参考以下内容: 进入主菜单界面,依次选择“投入运行”—“测量”—基坐标,选择“3点法”, 在系统弹出的基坐标编辑界面,给基座标编号为3,命名为table1,然后单击“继续”按钮,进行下一步操作, 在弹出的…...
以太网的MAC层
以太网的MAC层 一、硬件地址 局域网中,硬件地址又称物理地址或MAC地址(因为用在MAC帧),它是局域网上每一台计算机中固化在适配器的ROM中的地址。 关于地址问题,有这样的定义:“名字指出我们所要寻…...
Hadoop启动后jps发现没有DateNode解决办法
多次使用 Hadoop namenode -format 格式化节点后DateNode丢失 找到hadoop配置文件core-site.xml查找tmp路径 进入该路径,使用rm -rf data删除data文件 再次使用Hadoop namenode -format 格式化后jps后出现DateNode节点...
VUE3照本宣科——应用实例API与setup
VUE3照本宣科——应用实例API与setup 前言一、应用实例API1.createApp()2.app.use()3.app.mount() 二、setup 前言 👨💻👨🌾📝记录学习成果,以便温故而知新 “VUE3照本宣科”是指照着中文官网和菜鸟教…...
json/js对象的key有什么区别?
1.对于JS对象来说 一个js对象如果是这样的 obj {"0": "小明","0name": "小明明", "": 18,"¥": "哈哈"," ": "爱好广泛" }对于js对象来说,有时候key是不…...
极大似然估计概念的理解——统计学习方法
目录 1.最大似然估计的概念的理解1 2.最大似然估计的概念的理解2 3.最大似然估计的概念的理解3 4.例子 1.最大似然估计的概念的理解1 最大似然估计是一种概率论在统计学上的概念,是参数估计的一种方法。给定观测数据来评估模型参数。也就是模型已知,参…...
python模拟表格任意输入位置
在表格里输入数值,要任意位置,我找到了好方法: input输入 1. 行 2. 列输入:1 excel每行输入文字input输入位置 3.2 表示输入位置在:3行个列是要实现一个类似于 Excel 表格的输入功能,并且希望能够指定输入…...
如何限制文件只能通过USB打印机打印,限制打印次数和时限并且无法在打印前查看或编辑内容
在今天这个高度信息化的时代,文档打印已经成为日常工作中不可或缺的一部分。然而,这也带来了诸多安全风险,如文档被篡改、知识产权被侵犯以及信息泄露等。为了解决这些问题,只印应运而生。作为一款独特的软件工具,只印…...
车牌文本检测与识别:License Plate Recognition Based On Multi-Angle View Model
论文作者:Dat Tran-Anh,Khanh Linh Tran,Hoai-Nam Vu 作者单位:Thuyloi University;Posts and Telecommunications Institute of Technology 论文链接:http://arxiv.org/abs/2309.12972v1 内容简介: 1)方向&#x…...
Blender中的4种视图着色模式
Blender中有四种主要的视图着色模式:线框、实体、Look Dev和渲染。它们的主要区别如下: - 线框模式只显示物体的边缘(线框),可以让您看到场景中的所有物体,也可以调整线框的颜色和背景的颜色。 - 实…...
Flutter项目安装到Android手机一直显示在assembledebug
问题 Flutter项目安装到Android手机一直显示在assembledebug 原因 网络不好,gradle依赖下载不下来 解决方案 修改如下的文件 gradle-wrapper.properties 使用腾讯提供的gradle镜像下载 distributionUrlhttps://mirrors.cloud.tencent.com/gradle/gradle-7.5…...
数据挖掘实验(二)数据预处理【等深分箱与等宽分箱】
一、分箱平滑的原理 (1)分箱方法 在分箱前,一定要先排序数据,再将它们分到等深(等宽)的箱中。 常见的有两种分箱方法:等深分箱和等宽分箱。 等深分箱:按记录数进行分箱࿰…...
Vue2 第一次学习
本章为超级浓缩版,文章过于短,方便复习使用哦~ 文章目录 1. 简单引入 vue.js2. 指令2.1 事件绑定指令 v-on (简写 )2.2 内容渲染指令2.3 双向绑定指令 v-model2.4 属性绑定指令 v-bind (简写 : )2.5 条件渲染指令2.6 循环指令 v-for 3. vue 其他知识3.1 侦听器 watch3.2 计算属…...
tiny模式基本原理整合
【Tiny模式】的基本构成 M【首头在首位】 U【/】 V【HTTP/】 Host H【真实ip】 XH \r回车 \n换行 \t制表 \ 空格 一个基本的模式构成 [method] [uri] [version]\r\nHost: [host]\r\n[method] [uri] [version]\r\nHost: [host]\r\n 检测顺序 http M H XH 有些地区 XH H M 我这边…...
使用聚氨酯密封件的好处?
聚氨酯密封件因其优异的耐用性、灵活性和广泛的应用范围而在各个行业中广受欢迎。在本文中,我们将探讨使用聚氨酯密封件的优点,阐明其在许多不同领域广泛使用背后的原因。 1、高性能: 聚氨酯密封件具有出色的性能特征,使其成为各…...
DevEco Studio如何安装中文插件
首先 官网下载中文插件 由于DevEco是基于IntelliJ IDEA Community的,所有Compatibility选择“IntelliJ IDEA Community”,然后下载一个对应最新的就ok了。 最后打开Plugins页面,点击右上角齿轮 -> Install Plugin from Disk…。选择下载的…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
