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

【算法笔记】整除与最大公约数（GCD）专题整理

news 来源：原创 2025/8/17 21:40:54

参考文章链接（已获得作者授权）

一、整除：数学中的"完美分割"

定义
若整数 $a$ 能整除整数 $b$ （记作 $a\mid b$ ），则存在整数 $k$ 使得 $b=a\cdot k$ 。
通俗理解：将 $b$ 分割为若干份大小为 $a$ 的块，无剩余。

关键性质

符号等价性
$a\mid b\Leftrightarrow -a\mid b\Leftrightarrow a\mid -b\Leftrightarrow |a|\mid |b|$
例： $3\mid12$ 等价于 $-3\mid12$ 或 $3\mid-12$ 。
传递性
$a\mid b$ 且 $b\mid c\implies a\mid c$ 。
例： $3\mid6$ 且 $6\mid12\implies3\mid12$ 。
线性组合性
$a\mid b$ 且 $a\mid c\implies a\mid(xb+yc)$ （ $x,y\in\mathbb{Z}$ ）。
例： $5\mid10$ 和 $5\mid15\implies5\mid(2\cdot10+3\cdot15=65)$ 。
非零约束性
若 $b\neq0$ 且 $a\mid b$ ，则 $|a|\leq|b|$ 。
例： $7\mid14$ 且 $|7|\leq|14|$ 。

二、最大公约数（GCD）：寻找"最大共同因子"

定义
$\gcd(a,b)$ 是能同时整除 $a$ 和 $b$ 的最大正整数。
应用场景：均匀分配问题（如分糖、分饼干）。

示例

$\gcd(24,36)=12$
解释：24和36的公约数为1,2,3,4,6,12，最大的是12。

三、欧几里得算法（GCD计算）

核心思想：通过余数递归缩小问题规模。
步骤（以48和18为例）：

$48\div18=2$ 余12→转 $\gcd(18,12)$
$18\div12=1$ 余6→转 $\gcd(12,6)$
$12\div6=2$ 余0→终止， $\gcd=6$ 。

原理： $\gcd(a,b)=\gcd(b,a\bmod b)$ 。

四、贝祖定理：线性方程的整数解

定理内容
对任意整数 $a, b$ ，存在 $x,y\in\mathbb{Z}$ 使得：
$ax+by=\gcd(a,b)$

示例

$a = 48$ , $b = 18$ , $\gcd(48,18)=6$
解： $x = - 1$ , $y = 3$ （因 $48\cdot(-1)+18\cdot3=6$ ）。

应用：密码学（如RSA中计算模逆元）。

五、扩展欧几里得算法（ExGCD）

目标：求解贝祖等式中的 $x$ 和 $y$ 。
步骤（回溯法，以48和18为例）：

欧几里得过程：
$\begin{align*} 48&=18\times2+12\\ 18&=12\times1+6\\ 12&=6\times2+0\quad(\gcd=6) \end{align*}$
回代表达式：
$\begin{align*} 6&=18-12\times1\\ &=18-(48-18\times2)\times1\\ &=18\times3-48\times1 \end{align*}$
得 $x = - 1$ , $y = 3$ 。

递归逻辑：每一步用上一步的余数表示当前余数。

总结图表

概念	核心思想	示例
整除	无余数分割	$3\mid12$
GCD	最大共同因子	$\gcd(24,36)=12$
欧几里得算法	余数递归	$\gcd(48,18)=6$
贝祖定理	线性方程的整数解	$48 x + 18 y = 6$
ExGCD	回溯求解 $x, y$	$x = - 1$ , $y = 3$

注：所有性质与算法均基于整数运算，且 $b\neq0$ 时 $|a|\leq|b|$ 保证有限步终止。

【算法笔记】整除与最大公约数（GCD）专题整理

参考文章链接（已获得作者授权） 一、整除：数学中的"完美分割" 定义若整数 a a a能整除整数 b b b（记作 a ∣ b a\mid b a∣b），则存在整数 k k k使得 b a ⋅ k ba\cdot k ba⋅k。通俗理解&…...

编程日记 2025/8/17 21:40:54

JDBC 与 MyBatis 详解：从基础到实践

目录一、JDBC 介绍二、使用 JDBC 查询用户信息三、ResultSet 结果集四、预编译 SQL - SQL 注入问题五、预编译 SQL - 性能更高六、JDBC 增删改操作插入数据： 更新数据： 删除数据： 七、MyBatis 介绍八、MyBatis 入门程序引…...

编程日记 2025/8/17 21:26:53

虚拟机开发环境搭建与内网迁移

以下是关于在虚拟机中搭建开发环境并迁移至内网的详细步骤及注意事项，适用于需要在内网隔离环境中进行开发的场景（如企业安全要求、离线开发等）： ‌一、虚拟机开发环境搭建‌ ‌1. 选择虚拟机平台‌ ‌推荐工具‌： ‌V…...

编程日记 2025/8/17 21:08:22

【HFP】蓝牙HFP协议音频连接核心技术深度解析

目录一、音频连接建立的总体要求 1.1 发起主体与时机 1.2 前提条件 1.3 同步连接的建立 1.4 通知机制二、不同主体发起的音频连接建立流程 2.1 连接建立触发矩阵 2.2 AG 发起的音频连接建立 2.3 HF 发起的音频连接建立三、编解码器连接建立流程 3.1 发起条件 3.…...

编程日记 2025/8/17 18:16:37

PowerBI 表格显示无关联的表数据

假设有两张没有建立关联的数据表: 产品表库存表我们将他们放入表格里显示，数据会出问题。因为 [库存表] 里的数据有除 [产品表] 以外的产品的数据，所以PBI无法从两张表中找到一一对应的数据。解决方法:(不建立关联关系的情况下) 新建一个度量值&a…...

编程日记 2025/8/17 0:31:25

观察者模式详解与C++实现

1. 模式定义观察者模式（Observer Pattern）是一种行为型设计模式，定义了对象间的一对多依赖关系。当一个对象（被观察者/主题）状态改变时，所有依赖它的对象（观察者）都会自动收到通知…...

编程日记 2025/8/17 6:59:04

用ffmpeg 实现拉取h265的flv视频转存成264的mp4 实现方案

1.需要对ffmpeg进行源码修改这里使用 https://github.com/numberwolf/FFmpeg-QuQi-H265-FLV-RTMP 这位大神提供的源码需要 x265_3.2.1.tar.gz last_x264.tar.bz2 fdk-aac-2.0.1.tar.gz FFmpeg-QuQi-H265-FLV-RTMP-master.zip 这些包升级ubuntu18.04 apt update a…...

编程日记 2025/8/17 18:16:42

《AI赋能职场：大模型高效应用课》第8课 AI辅助职场沟通与协作

【本课目标】掌握AI辅助邮件、沟通话术的优化技巧。学习利用AI快速生成高效的会议纪要。通过实操演练，提升职场沟通效率与协作能力。【准备工具】 DeepSeek大模型（deepseek.com）百度文心一言（yiyan.baidu.com） 一…...

编程日记 2025/8/17 20:54:09

PowerBI下载安装教程

1、打开官方下载链接，或者Microsoft store里搜索下载（通过官网下载可以选择安装路径，应用商店直接会安装到默认路径里）。 2、等待下载成功后，直接点击【打开】即可。...

编程日记 2025/8/17 20:53:23

PowerBI如何钻取到明细

PowerBI如何钻取到明细最近做项目领导提到一需求，在查看账龄的时候，还想查看到它的一个明细情况。 PowerBI如何钻取到明细，以一个案例分享下： 第一步：我们先查看账龄的一个分布情况： 第二步：…...

编程日记 2025/8/17 21:40:58

常见算法题

import java.util.*;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;} }public class test_04_16 {//获取二叉…...

编程日记 2025/8/14 9:52:06

C语言超详细结构体知识

1.自定义类型：结构体的介绍在之前的博客中，我们简单介绍过了关于结构体的基本知识，这里我们稍微复习一下。结构体(struct)是C语言中一种重要的复合数据类型，它允许将不同类型的数据组合成一个整体。 1.1结构体的定义结构体使…...

编程日记 2025/8/17 21:28:52

2N60-ASEMI功业控制与自动化专用2N60

编辑：ll 2N60-ASEMI功业控制与自动化专用2N60 型号：2N60 品牌：ASEMI 封装：TO-220F 批号：最新最大漏源电流：2A 漏源击穿电压：600V RDS（ON）Max：5.00Ω…...

编程日记 2025/8/17 18:16:50

发现“横”字手写有难度，对比两个“横”字

我发现手写体“横”字“好看”程度，难以比得上印刷体： 两个从方正简体启体来的“横”字： 哪个更好看？我是倾向于左边一点。 <div style"transform: rotate(180deg); display: inline-block;"> 左边是我从方正简…...

编程日记 2025/8/17 7:16:23

深入解析 HTML5 Web IndexedDB 数据库：构建高效离线应用的基石

摘要在现代 Web 应用开发中，离线访问和高效处理大量结构化数据的需求日益增长。HTML5 的 IndexedDB 作为一种强大的客户端 NoSQL 数据库，为开发者提供了可靠的解决方案。本文将全面介绍 IndexedDB 的特性、语法、方法、应用实例、使用场景，以及其优势与劣势，帮助开发者深…...

编程日记 2025/8/17 20:16:17

17-算法打卡-哈希表-快乐数-leetcode(202)-第十七天

1 题目地址 202. 快乐数 - 力扣（LeetCode）202. 快乐数 - 编写一个算法来判断一个数 n 是不是快乐数。「快乐数」定义为： * 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。 * 然后重复这个过程直到这个数变为 1…...

编程日记 2025/8/17 20:26:55

决战浏览器渲染：减少重绘（Repaint）与重排（Reflow）的性能优化策略

在现代Web开发中，流畅的用户体验是衡量应用质量的关键指标之一。用户与界面的每一次交互，背后都牵动着浏览器复杂而精密的渲染过程。当这个过程不够高效时，用户就会感受到卡顿、延迟，甚至页面“掉帧”。在众多影响渲染性能的因素中…...

编程日记 2025/8/17 21:37:04

深度解析生成对抗网络：原理、应用与未来趋势

在人工智能的浩瀚星空中，生成对抗网络（Generative Adversarial Networks，GAN）犹如一颗璀璨的明星，自 2014 年由 Ian Goodfellow 等人提出以来，便以其独特而强大的生成能力，在计算机视觉、自然语…...

编程日记 2025/8/17 18:17:00

电能质量治理解决方案：构建高效、安全的电力系统

随着“双碳”目标的推进及新型电力系统的快速发展，大量电力电子设备（如光伏逆变器、充电桩、变频器等）接入电网，导致谐波畸变、无功功率激增、电压波动等问题日益突出。电能质量恶化不仅威胁设备安全，还影响电网稳定运…...

编程日记 2025/8/17 18:16:45

生态篇｜多总线融合与网关设计

引言 1. 车内多总线概览 2. 主流车载总线技术对比 3. 网关设计原则与架构 4. 协议转换与映射策略 5. 安全与诊断功能集成...

编程日记 2025/8/17 21:39:50

HDFS入门】HDFS安全与权限管理解析：从认证到加密的完整指南

目录引言 1 认证与授权机制 1.1 Kerberos认证集成 1.2 HDFS ACL细粒度控制 2 数据加密保护 2.1 传输层加密(SSL/TLS) 2.2 静态数据加密 3 审计与监控体系 3.1 操作审计流程 3.2 安全监控指标 4 权限模型详解 4.1 用户/组权限模型 4.2 umask配置原理 5 安全最佳实…...

编程日记 2025/8/17 21:34:19

合成数据中的对抗样本生成与应用：让AI模型更强、更稳、更安全

目录合成数据中的对抗样本生成与应用：让AI模型更强、更稳、更安全一、什么是对抗样本？ 二、为什么要在合成数据中引入对抗样本？ 三、对抗样本在图像合成数据中的生成方法 ✅ 方法1：FGSM（Fast Gradient Sign Met…...

编程日记 2025/8/17 21:13:01

考研系列-计算机网络-第二章、物理层

一、通信基础 1.物理层基本概念 2.数据通信基础知识...

编程日记 2025/8/17 21:19:50

uni-app 安卓10以上上传原图解决方案

在Android 10及以上版本中，由于系统对文件访问的限制，使用chooseImage并勾选原图上传后，返回的是图片的外部存储路径，如：file:///storage/emulated/0/DCIM/Camera/。这种外部存储路径，无法直接转换成所需要…...

编程日记 2025/8/17 18:16:48

关于element的dialog的取消(关闭弹窗)方法触发两次

在这里插入图片描述关闭的时候加个修饰符.native close.native...

编程日记 2025/8/17 20:11:31

vue，uniapp解决h5跨域问题

如果有这样的跨域问题，解决办法： ✅ 第一步：在项目根目录下创建 vue.config.js 和 package.json 同级目录。 // vue.config.js module.exports {devServer: {proxy: {/api: {target: https://app.yycjkb.cn, // 你的后端接口地址changeOrig…...

编程日记 2025/8/17 20:12:05

2025-04-18 李沐深度学习3 —— 线性代数

文章目录 1 线性代数1.1 标量、向量与矩阵1.2 矩阵概念1.3 按特定轴求和 2 实战：线性代数2.1 标量2.2 向量2.3 矩阵2.4 张量2.5 降维2.6 点积2.7 矩阵-向量积2.8 矩阵-矩阵乘法2.9 范数2.10 练习 1 线性代数 1.1 标量、向量与矩阵标量（Scalar&#xff…...

编程日记 2025/8/17 20:46:14

2026《数据结构》考研复习笔记三（C++高级教程）

C高级教程一、文件和流二、异常处理三、命名空间四、模板五、信号处理六、多线程一、文件和流 iostream 用于标准输入/输出（控制台I/O），处理与终端（键盘输入和屏幕输出）的交互包含以下全局流对象： cin&…...

编程日记 2025/8/17 18:16:54

python进阶: 深入了解调试利器 Pdb

Python是一种广泛使用的编程语言，以其简洁和可读性著称。在开发和调试过程中，遇到错误和问题是不可避免的。Python为此提供了一个强大的调试工具——Pdb（Python Debugger）。 Pdb是Python标准库中自带的调试器，可以帮助…...

编程日记 2025/8/17 20:13:54

前端资源加载失败后重试加载(CSS,JS等引用资源)

前端资源加载失败后的重试 .前端引用资源时出现了资源加载失败(这里针对的是路径引用异常或者url解析错误时) 解决这个问题首先要明确一下几个步骤 1.什么情况或者什么时候重试 2.如何重试 3.重试过程中的边界处理这里引入里三个测试脚本，分别加载里三个不同的脚…...

编程日记 2025/8/17 20:29:17

每日算法【双指针算法】(Day 2-复写零)

双指针算法 1.算法题目(复写零)2.讲解算法原理3.编写代码 1.算法题目(复写零) 注意：不要越界，不能开额外的数组，只能从现有数组上进行操作，没有返回值。 2.讲解算法原理解法：双指针操作先根据“异地”操作&#xf…...

编程日记 2025/8/17 2:04:12

【C++深入系列】：模版详解（上）

🔥 本文专栏：c 🌸作者主页：努力努力再努力wz 💪 今日博客励志语录： 你不需要很厉害才能开始，但你需要开始才能很厉害。 ★★★ 本文前置知识： 类和对象（上） …...

编程日记 2025/8/17 20:16:02

PyCharm Flask 使用 Tailwind CSS v3 配置

安装 Tailwind CSS 步骤 1：初始化项目在 PyCharm 终端运行：npm init -y安装 Tailwind CSS：npm install -D tailwindcss3 postcss autoprefixer初始化 Tailwind 配置文件：npx tailwindcss init这会生成 tailwind.config.js。步…...

编程日记 2025/8/17 18:16:46

设计模式每日硬核训练 Day 15：享元模式（Flyweight Pattern）完整讲解与实战应用

🔄 回顾 Day 14：组合模式小结在 Day 14 中，我们学习了组合模式（Composite Pattern）： 适用于构建树状层级结构，使得“单个对象”和“对象集合”统一操作。广泛用于文件系统、UI 控件树、组织结…...

编程日记 2025/8/17 20:24:47

使用Service发布应用程序

使用Service发布应用程序文章目录使用Service发布应用程序[toc]一、什么是Service二、通过Endpoints理解Service的工作机制1.什么是Endpoints2.创建Service以验证Endpoints 三、Service的负载均衡机制四、Service的服务发现机制五、定义Service六、Service类型七、无头Servic…...

编程日记 2025/8/17 20:33:52

美家市场2025电视版分享码-美家市场电视直播软件分享码免费获取

美家市场2025电视版作为一款备受欢迎的应用市场，为用户提供了海量的电视直播软件，而分享码则是免费获取这些资源的重要途径。与此同时，乐看家桌面也是一款在智能电视领域极具特色的软件，它能与美家市场搭配使用，为用户…...

编程日记 2025/8/17 18:16:56

动手学深度学习：手语视频在NiN模型中的测试

前言 NiN模型是在LeNet的基础上修改，提出了1x1卷积层和全局平均池化层的概念，减少了全连接所带来的参数量很多的问题。本篇在之前代码的基础上添加了模型保存，loss和acc记录以及记录模型时间等功能，所以模型后面的代码会重新记录…...

编程日记 2025/8/17 20:59:30

医院数据中心智能化数据上报与调数机制设计

针对医院数据中心的智能化数据上报与调数机制设计，需兼顾数据安全性、效率性、合规性及智能化能力。以下为系统性设计方案，分为核心模块、技术架构和关键流程三部分：一、核心模块设计 1. 数据上报模块子模块功能描述多源接入层对接HIS/LIS/PACS/EMR等异构系统，支持API/E…...

编程日记 2025/8/17 20:17:59

Ubuntu命令速查

当你在Ubuntu系统中需要快速查询常用命令时，可以使用以下速查表： 列出文件和目录： ls切换目录： cd [目录路径]显示当前工作目录的绝对路径： pwd创建新目录： mkdir [目录名]删除文件或目录： rm […...

编程日记 2025/8/17 20:56:25

一次制作参考网杂志的阅读书源的实操经验总结（附书源）

文章目录一、背景介绍二、书源文件三、详解制作书源（一）打开Web服务（二）参考网结构解释（三）阅读书源基础（四）阅读书源发现（五）阅读书源详细（六…...

编程日记 2025/8/17 18:16:51

python抓取HTML页面数据+可视化数据分析（投资者数量趋势）

本文所展示的代码是一个完整的数据采集、处理与可视化工具，主要用于从指定网站下载Excel文件，解析其中的数据，并生成投资者数量的趋势图表。以下是代码的主要功能模块及其作用： 1.网页数据获取使用fetch_html_page函数从目标网…...

编程日记 2025/8/17 20:24:15

下拉框select标签类型

在我们很多页面里有下拉框的选择，这种元素怎么定位呢？下拉框分为两种类型：我们分别针对这两种元素进行定位和操作 select标签 ： 通过select类处理。非select标签 1、针对下拉框元素，如果是Select标签类型，…...

编程日记 2025/8/17 21:33:54

嵌入式C语言位操作的几种常见用法

作为一名老单片机工程师，我承认，当年刚入行的时候，最怕的就是看那些密密麻麻的寄存器定义，以及那些让人眼花缭乱的位操作。尤其是遇到那种“明明改了寄存器，硬件就是不听话”的情况，简直想把示波器砸了&am…...

编程日记 2025/8/17 21:04:36

数据库原理及应用mysql版陈业斌实验四

🏝️专栏：Mysql_猫咪-9527的博客-CSDN博客 🌅主页：猫咪-9527-CSDN博客 “欲穷千里目，更上一层楼。会当凌绝顶，一览众山小。” 目录实验四索引与视图 1.实验数据如下 student 表（学生表&…...

编程日记 2025/8/17 21:38:27

【免登录ORACLE，jdk8安装包下载】jdk-8u441-windows-i586.exe和jdk-8u441-windows-x64.exe有什么区别

jdk-8u441-windows-i586.exe和jdk-8u441-windows-x64.exe主要有以下区别： 我用夸克网盘分享了「jdk」，链接：https://pan.quark.cn/s/c72666843e2b 适用系统架构： jdk-8u441-windows-i586.exe适用于32位的Windows操作系统&#x…...

编程日记 2025/8/17 4:42:19