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

【算法学习笔记】35：扩展欧几里得算法求解线性同余方程

news 来源：原创 2025/6/8 8:07:40

线性同余方程问题

线程同余方程问题是指 $\equiv b~(mod~m)$ ，给定 $a$ 、 $b$ 和 $m$ ，找到一个整数 $x$ 使得该方程成立，即使得 $a x m o d m = b$ ，随便返回任何一个解都可以。

例如 $\equiv 3~(mod~5)$ ，那么 $x$ 的一个可能的解可以是 $2$ 。

接下来用扩展欧几里得算法尝试构造这个解。从 $\equiv b~(mod~m)$ 可知，一定存在一个 $y$ 使得：
$\cdot x = m \cdot y + b$

也就是说，因为 $a x$ 模 $m$ 的余数是 $b$ ，所以 $a x$ 一定可以表示成 $m$ 的整数 $y$ 倍再加上一个 $b$ 。也就是：
$a x - m y = b$

令 $y^{'} = y$ ，那么就是：
$a x + m y^{'} = b$

因此原线性同余方程问题求 $x$ 有解，等价于这个方程求 $x$ 和 $y^{'}$ 有解。而根据扩展欧几里得算法里所讨论的， $a$ 是 $g c d (a, m)$ 的倍数， $m$ 也是 $g c d (a, m)$ 的倍数，所以它们拼到一起也必须是 $g c d (a, m)$ 的倍数。

因此，这个方程有解的充要条件是 $b$ 必须是 $g c d (a, m)$ 的倍数，也即 $g c d (a, m) ∣ b$ 。

例题：AcWing 878. 线性同余方程

这题最终结果要限制在int范围内，因为 $m$ 也是在int范围内的，并且：
$\\ \Leftrightarrow a(km + r) + my = b \\ \Leftrightarrow ar + m(ak + y) = b$
也就是说，把系数 $x$ 变成 $r = x m o d m$ 时，另一个系数只要从 $y$ 变成 $ak + y$ 就可以了，其中 $\lfloor \frac{x}{m} \rfloor$ 。

所以可以直接把结果 $x$ 模 $m$ ，一定也是一个合法的解，并且满足在int范围内的要求。

#include <iostream>using namespace std;typedef long long LL;int exgcd(int a, int b, int& x, int& y) {if (!b) {x = 1, y = 0;return a;}int d = exgcd(b, a % b, y, x);// d = b * y + (a % b) * x = b * y + (a - a / b * b) * x//   = a * x + b * (y - a / b * x)y -= a / b * x;return d;
}int main() {int t; cin >> t;while (t -- ) {int a, b, m; cin >> a >> b >> m;// ax % m = b, ax + my' = b, iff gcd(a, m) = d | bint x, y;int d = exgcd(a, m, x, y);if (b % d) puts("impossible");else cout << (LL)x * (b / d) % m << endl;}return 0;
}

【算法学习笔记】35：扩展欧几里得算法求解线性同余方程

线性同余方程问题线程同余方程问题是指 a x ≡ b ( m o d m ) ax \equiv b~(mod~m) ax≡b (mod m)，给定 a a a、 b b b和 m m m，找到一个整数 x x x使得该方程成立，即使得 a x m o d m b ax~mod~mb ax mod mb，随便返回任何一个…...

编程日记 2025/5/31 21:02:52

ent.SetDatabaseDefaults()

在 AutoCAD 的 .NET API 中，ent.SetDatabaseDefaults() 这句代码通常用于将一个实体（Entity）对象的属性设置为与其所在的数据库（Database）的默认设置相匹配。这意味着，该实体将采用数据库级别的默认颜色、图…...

编程日记 2025/6/2 22:13:57

使用docker部署tomcat服务器和mysql数据库

使用docker部署tomcat服务器 1、拉去tomcat镜像 [rootlocalhost yum.repos.d]# sudo docker pull docker.io/tomcat:9 9: Pulling from library/tomcat de44b265507a: Pull complete 4c2afd91a87d: Pull complete 89e9bbcfa697: Pull complete 11be3e613582: Pull complet…...

编程日记 2025/5/29 4:44:34

Jenkins 启动

废话这一阵子感觉空虚，心里空捞捞的，总想找点事情做，即使这是一件微小的事情，空余时间除了骑车、打球，偶尔朋友聚会 … 还能干什么呢？ 当独自一人时，究竟可以做点什么，填补这空虚…...

编程日记 2025/6/3 16:16:19

Elasticsearch（ES）基础查询语法的使用

1. Match Query (全文检索查询) 用于执行全文检索，适合搜索文本字段。 { “query”: { “match”: { “field”: “value” } } } match_phrase：精确匹配短语，适合用于短语搜索。 { “query”: { “match_phrase”: { “field”: “text” }…...

编程日记 2025/6/1 19:07:07

SpringCloud系列教程：微服务的未来（十四）网关登录校验、自定义过滤器GlobalFilter、GatawayFilter

前言在微服务架构中，API 网关扮演着至关重要的角色，负责路由请求、执行安全验证、流量控制等任务。Spring Cloud Gateway 作为一个强大的网关解决方案，提供了灵活的方式来实现这些功能。本篇博客将重点介绍如何在 Spring Cloud Gateway 中…...

编程日记 2025/6/2 6:49:36

Android Studio：Linux环境下安装与配置

更多内容：XiaoJ的知识星球 Android Studio：Linux环境下安装与配置 1.安装JDK2.安装Android Studio2.1 获取安装包2.2 安装（1）配置环境变量：（2）运行安装：（3）配…...

编程日记 2025/6/3 4:58:22

使用AI生成金融时间序列数据：解决股市场的数据稀缺问题并提升信噪比

“GENERATIVE MODELS FOR FINANCIAL TIME SERIES DATA: ENHANCING SIGNAL-TO-NOISE RATIO AND ADDRESSING DATA SCARCITY IN A-SHARE MARKET” 论文地址：https://arxiv.org/pdf/2501.00063 摘要金融领域面临的数据稀缺与低信噪比问题，限制了深度学习在…...

编程日记 2025/6/3 6:31:09

【银河麒麟高级服务器操作系统】业务访问慢网卡丢包现象分析及处理过程

了解更多银河麒麟操作系统全新产品，请点击访问麒麟软件产品专区：product.kylinos.cn 开发者专区：developer.kylinos.cn 文档中心：document.kylinos.cn 交流论坛：forum.kylinos.cn 服务器环境以及配置【内核版本…...

编程日记 2025/6/2 18:01:24

如何将数据库字符集改为中文，让今后所有的数据库都支持中文

最后一行有我自己的my.ini文件数据库输入中文数据时会变为乱码， 这个时候，我们为每个数据库设置字符集，太过于麻烦，为数据库单独设置重启后又会消失 Set character_set_database’utf8’; Set character_set_server’utf8’; …...

编程日记 2025/6/4 8:44:14

Linux-C/C++--深入探究文件 I/O (下)(文件共享、原子操作与竞争冒险、系统调用、截断文件)

经过上一章内容的学习，了解了 Linux 下空洞文件的概念；open 函数的 O_APPEND 和 O_TRUNC 标志；多次打开同一文件；复制文件描述符；等内容本章将会接着探究文件IO，讨论如下主题内容。  文件共享介绍&…...

编程日记 2025/5/28 9:02:57

Linux Bash 中使用重定向运算符的 5 种方法

注：机翻，未校。 Five ways to use redirect operators in Bash Posted: January 22, 2021 | by Damon Garn Redirect operators are a basic but essential part of working at the Bash command line. See how to safely redirect input and output t…...

编程日记 2025/6/2 6:49:00

opengrok_windows_环境搭建

目录软件列表软件安装工程索引编辑工程部署问题列表软件列表软件名下载地址用途JDKhttps://download.java.net/openjdk/jdk16/ri/openjdk-1636_windows-x64_bin.zipindex 使用java工具tomcathttps://dlcdn.apache.org/tomcat/tomcat-9/v9.0.98/bin/apache-tom…...

编程日记 2025/6/3 16:21:59

【无法下载github文件】虚拟机下ubuntu无法拉取github文件

修改hosts来进行解决。步骤一：打开hosts文件 sudo vim /etc/hosts步骤二：查询 github.com的ip地址 https://sites.ipaddress.com/github.com/#ipinfo将github.com的ip地址添加到hosts文件末尾，如下所示。 140.82.114.3 github.com步骤三…...

编程日记 2025/6/2 17:53:19

python——句柄

一、概念句柄指的是操作系统为了标识和访问对象而提供的一个标识符，在操作系统中，每个对象都有一个唯一的句柄，通过句柄可以访问对象的属性和方法。例如文件、进程、窗口等都有句柄。在编程中，可以通过句柄来操作这些对象&#x…...

编程日记 2025/6/2 19:14:01

.Net Core微服务入门系列（一）——项目搭建

系列文章目录 1、.Net Core微服务入门系列（一）——项目搭建 2、.Net Core微服务入门全纪录（二）——Consul-服务注册与发现（上） 3、.Net Core微服务入门全纪录（三）——Consul-服务注…...

编程日记 2025/6/3 16:23:19

Net Core微服务入门全纪录（三）——Consul-服务注册与发现（下）

编程日记 2025/6/3 16:23:51

[苍穹外卖] 1-项目介绍及环境搭建

项目介绍定位：专门为餐饮企业（餐厅、饭店）定制的一款软件产品功能架构： 管理端 - 外卖商家使用用户端 - 点餐用户使用技术栈： 开发环境的搭建整体结构： 前端环境前端工程基于 nginx 运行 - Ngi…...

编程日记 2025/6/3 16:22:16

【PCIe 总线及设备入门学习专栏 2 -- PCIe 的 LTSSM 和 Enumeration】

文章目录 OverviewLTSSM StatesDetect StatesDETECT_QUIETDETECT_ACTDETECT_WAITPolling StatesPOLL_ACTIVEPOLL_CONFIGPOLL_COMPLIANCEConfiguration StatesCONFIG_LINKWD_STARTCONFIG_LINKWD_ACCEPTCONFIG_LANENUM_WAITCONFIG_LANENUM_ACCEPTCONFIG_COMPLETECONFIG_IDLERecov…...

编程日记 2025/6/3 13:56:47

Redis 性能优化：多维度技术解析与实战策略

文章目录 1 基准性能2 使用 slowlog 优化耗时命令3 big key 优化4 使用 lazy free 特性5 缩短键值对的存储长度6 设置键值的过期时间7 禁用耗时长的查询命令8 使用 Pipeline 批量操作数据9 避免大量数据同时失效10 客户端使用优化11 限制 Redis 内存大小12 使用物理机而非虚拟机…...

编程日记 2025/6/3 16:23:35

QT开发技术【基于TinyXml2的对类进行序列化和反序列化】一

一、对TinyXml2 进行封装使用宏实现序列化和反序列化思路： 利用宏增加一个类函数，使用序列化器调用函数进行序列化封装宏示例 #define XML_SERIALIZER_BEGIN(ClassName) \ public: \virtual void ToXml(XMLElement* parentElem, bool bSerialize …...

编程日记 2025/6/3 16:22:32

麦田物语学习笔记:创建TransitionManager控制人物场景切换

基本流程制作场景之间的切换 1.代码思路 (1)为了实现不同场景切换,并且保持当前的persistentScene一直存在,则需要一个Manager去控制场景的加载和卸载,并且在加载每一个场景之后,都要将当前的场景Set Active Scene,保证其为激活的场景,在卸载的时候也可以方便调用当前激活的场…...

编程日记 2025/6/3 16:23:04

2025年最新汽车零部件企业销售项目管理解决方案

在汽车零部件企业，销售项目管理的不规范和销售预测的不准确性常导致生产计划无法及时调整，因此客户关系常常中断，导致企业业务机会的丧失。为解决该问题，企业需要投入更多资源以优化销售流程与销售预测。 1、360多维立体客户视图…...

编程日记 2025/6/3 6:31:09

创建基于Prism框架的WPF应用（NET Framework）项目

创建基于Prism框架的WPF应用（NET Framework）项目 1、创建WPF（NET Framework）项目并整理结构 （1）、创建WPF（NET Framework）项目； （2）、添加Views和…...

编程日记 2025/6/3 16:06:26

AIGC视频生成模型：Meta的Emu Video模型

大家好，这里是好评笔记，公主号：Goodnote，专栏文章私信限时Free。本文详细介绍Meta的视频生成模型Emu Video，作为Meta发布的第二款视频生成模型，在视频生成领域发挥关键作用。 🌺优质专栏回顾&am…...

编程日记 2025/6/3 16:08:49

【PowerQuery专栏】PowerQuery提取XML数据

XML数据和Json 数据类型都是比较典型的层次数据类型，XML的数据格式非常的对称。所有的数据均是由标签对组成，图为典型的XML文件类型的数据。在PowerQuery中进行XML数据类型解析采用的是Xml.Document 函数来进行文件内容的解析，Xml.Document 目前有三个可用参数。参数1为数…...

编程日记 2025/6/4 1:49:38

流行的开源高性能数据同步工具 - Apache SeaTunnel 整体架构运行原理

概述背景数据集成在现代企业的数据治理和决策支持中扮演着至关重要的角色。随着数据源的多样化和数据量的迅速增长，企业需要具备强大的数据集成能力来高效地处理和分析数据。SeaTunnel通过其高度可扩展和灵活的架构，帮助企业快速实现多源数据的采集、…...

编程日记 2025/6/3 16:08:33

基于单片机的多功能蓝牙语音智能台灯（论文+源码）

1总体方案设计通过需求分析，本设计多功能蓝牙语音智能台灯的系统框图如图2.1所示，系统架构包括主控制器STM32F103单片机、HC-06蓝牙通信模块、LU-ASR01语音识别模块、OLED液晶、LED灯、按键等器件，在使用时用户可以通过手机APP、语音识别、…...

编程日记 2025/6/3 16:06:57

leetcode刷题记录（七十二）——146. LRU 缓存

（一）问题描述 146. LRU 缓存 - 力扣（LeetCode）146. LRU 缓存 - 请你设计并实现一个满足 LRU (最近最少使用) 缓存 [https://baike.baidu.com/item/LRU] 约束的数据结构。实现 LRUCache 类： * LRUCache(int capacity)…...

编程日记 2025/6/3 16:07:29

力扣203题（3）

题目及之前的两种解法大家可以移步到这里： https://blog.csdn.net/suibiansa_/article/details/145242573?spm1001.2014.3001.5501 力扣203题—— 移除链表元素-CSDN博客今天呢我们来写一下第三种解法： 虚拟创建一个头结点 ListNode firstnew Lis…...

编程日记 2025/6/2 18:37:00

网络安全：信息时代的守护者

随着互联网的快速发展，网络安全问题日益成为全球关注的焦点。无论是个人用户、企业组织还是政府部门，网络安全都已成为保障信息安全、保护隐私、确保社会秩序的基石。在这个数字化时代，如何应对复杂多变的网络安全威胁，成为了我们…...

编程日记 2025/6/4 6:49:37

【博客之星2024年度总评选】年度回望：我的博客之路与星光熠熠

【个人主页】Francek Chen 【人生格言】征途漫漫，惟有奋斗！ 【热门专栏】大数据技术基础 | 数据仓库与数据挖掘 | Python机器学习文章目录前言一、个人成长与盘点（一）机缘与开端（二）收获与分享二、年度创…...

编程日记 2025/6/2 22:45:56

接口自动化测试

APITEST: 接口自动化测试目录结构介绍： conf目录：用来存放项目运行环境、执行环境相关的配置参数 testsuite目录：测试用例在此目录编写，pytest默认约定test开头的文件和方法为测试用例，不满足条件的不会被执行&#x…...

编程日记 2025/6/2 3:44:11

题海拾贝：力扣 138.随机链表的复制

Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！ 我的博客：<但凡. 我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》欢迎点赞，关注！ 1、题…...

编程日记 2025/6/1 5:37:53

第7章：Python TDD测试Franc对象乘法功能

写在前面这本书是我们老板推荐过的，我在《价值心法》的推荐书单里也看到了它。用了一段时间 Cursor 软件后，我突然思考，对于测试开发工程师来说，什么才更有价值呢？如何让 AI 工具更好地辅助自己写代码，或许…...

编程日记 2025/6/1 11:32:48

PyTorch基本功能与实现代码

PyTorch是一个开源的深度学习框架，提供了丰富的函数和工具，以下为其主要功能的归纳： 核心数据结构： • 张量（Tensor）：类似于Numpy的ndarray，是PyTorch中基本的数据结构&#xff0c…...

编程日记 2025/6/3 18:50:14

【2024 CSDN博客之星】技术洞察类：从DeepSeek-V3的成功，看MoE混合专家网络对深度学习算法领域的影响（MoE代码级实战）

目录一、引言 1.1 本篇文章侧重点 1.2 技术洞察—MoE（Mixture-of-Experts，混合专家网络） 二、MoE（Mixture-of-Experts，混合专家网络） 2.1 技术原理 2.2 技术优缺点 2.3 业务代码实践 2.3.1 业务场…...

编程日记 2025/6/1 20:08:45

Single-Model and Any-Modality for Video Object Tracking——2024——cvpr-阅读笔记

Single-Model and Any-Modality for Video Object Tracking 摘要相关工作创新处MethodShared embeddingModal promptingRGB Tracker based on TransformerOverall ExperiimentDatasetRGB-D samples are sourced from DepthTrackRGB-T samples are extracted from LasHeRRGB-E s…...

编程日记 2025/6/1 23:30:50

线性同余方程问题

例题：AcWing 878. 线性同余方程

相关文章：