中国剩余定理及扩展
目录
中国剩余定理解释
中国剩余定理扩展——求解模数不互质情况下的线性方程组:
代码实现:
互质:
非互质:
中国剩余定理解释
在《孙子算经》中有这样一个问题:“今有物不知其数,三三数之剩二(除以3余2),五五数之剩三(除以5余3),七七数之剩二(除以7余2),问物几何?”这个问题称为“孙子问题”,该问题的一般解法国际上称为“中国剩余定理”。具体解法分三步:
-
- 找出三个数:从3和5的公倍数中找出被7除余1的最小数15,从3和7的公倍数中找出被5除余1 的最小数21,最后从5和7的公倍数中找出除3余1的最小数70。
- 用15乘以2(2为最终结果除以7的余数),用21乘以3(3为最终结果除以5的余数),同理,用70乘以2(2为最终结果除以3的余数),然后把三个乘积相加15∗2+21∗3+70∗2得到和233。
- 用233除以3,5,7三个数的最小公倍数105,得到余数23,即233%105=23。这个余数23就是符合条件的最小数。
就这么简单。我们在感叹神奇的同时不禁想知道古人是如何想到这个方法的,有什么基本的数学依据吗?
我们将“孙子问题”拆分成几个简单的小问题,从零开始,试图揣测古人是如何推导出这个解法的。
首先,我们假设n1是满足除以3余2的一个数,比如2,5,8等等,也就是满足3∗k+2(k>=0)的一个任意数。同样,我们假设n2是满足除以5余3的一个数,n3是满足除以7余2的一个数。
有了前面的假设,我们先从n1这个角度出发,已知n1满足除以3余2,能不能使得n1+n2的和仍然满足除以3余2?进而使得n1+n2+n3的和仍然满足除以3余2?
这就牵涉到一个最基本数学定理,如果有a%b=c,则有(a+k∗b)%b=c(k为非零整数),换句话说,如果一个除法运算的余数为c,那么被除数与kk倍的除数相加(或相减)的和(差)再与除数相除,余数不变。这个是很好证明的。
以此定理为依据,如果n2是3的倍数,n1+n2就依然满足除以3余2。同理,如果n3也是3的倍数,那么n1+n2+n3的和就满足除以3余2。这是从n1的角度考虑的,再从n2,n3的角度出发,我们可推导出以下三点:
-
- 为使n1+n2+n3的和满足除以3余2,n2和n3必须是3的倍数。
- 为使n1+n2+n3的和满足除以5余3,n1和n3必须是5的倍数。
- 为使n1+n2+n3的和满足除以7余2,n1和n2必须是7的倍数。
因此,为使n1+n2+n3的和作为“孙子问题”的一个最终解,需满足:
- n1除以3余2,且是5和7的公倍数。
- n2除以5余3,且是3和7的公倍数。
- n3除以7余2,且是3和5的公倍数。
所以,孙子问题解法的本质是从5和7的公倍数中找一个除以3余2的数n1,从3和7的公倍数中找一个除以5余3的数n2,从3和5的公倍数中找一个除以7余2的数n3,再将三个数相加得到解。在求n1,n2,n3时又用了一个小技巧,以n1为例,并非从5和7的公倍数中直接找一个除以3余2的数,而是先找一个除以3余1的数,再乘以2。也就是先求出5和7的公倍数模3下的逆元,再用逆元去乘余数。
这里又有一个数学公式,如果a%b=c,那么(a∗k)%b=a%b+a%b+…+a%b=c+c+…+c=k∗c(k>0),也就是说,如果一个除法的余数为c,那么被除数的k倍与除数相除的余数为k∗c。展开式中已证明。
最后,我们还要清楚一点,n1+n2+n3只是问题的一个解,并不是最小的解。如何得到最小解?我们只需要从中最大限度的减掉掉3,5,7的公倍数105即可。道理就是前面讲过的定理“如果a%b=ca%b=c,则有(a−k∗b)%b=c(a−k∗b)%b=c”。所以(n1+n2+n3)%105就是最终的最小解。
这样一来就得到了中国剩余定理的公式:
设正整数两两互素,则同余方程组
有整数解。并且在模下的解是唯一的,解为
其中,而为模的逆元。
中国剩余定理扩展——求解模数不互质情况下的线性方程组:
普通的中国剩余定理要求所有的互素,那么如果不互素呢,怎么求解同余方程组?
这种情况就采用两两合并的思想,假设要合并如下两个方程:
那么得到:
我们需要求出一个最小的xx使它满足:
那么x1和x2就要尽可能的小,于是我们用扩展欧几里得算法求出x1的最小正整数解,将它代回a1+m1x1,得到xx的一个特解x′,当然也是最小正整数解。
所以xx的通解一定是x′加上lcm(m1,m2)∗klcm(m1,m2)∗k,这样才能保证x模m1和m2的余数是a1和a2。由此,我们把这个x′当做新的方程的余数,把lcm(m1,m2)当做新的方程的模数。(这一段是关键)
合并完成:
代码实现:
互质:
//求M%A=a,M%B=b,...中的M,其中A,B,C...互质
int CRT(int a[],int m[],int n){ int M = 1; int ans = 0; for(int i=1; i<=n; i++) M *= m[i]; for(int i=1; i<=n; i++){ int x, y; int Mi = M / m[i]; ex_gcd(Mi, m[i], x, y); ans = (ans + Mi * x * a[i]) % M; } if(ans < 0) ans += M; return ans;
}
非互质:
bool merge(LL a1, LL m1, LL a2, LL m2, LL &a3, LL &m3) { LL d = gcd(m1, m2); LL c = a2 - a1; if(c % d) return false; c = (c % m2 + m2) % m2; m1 /= d; m2 /= d; c /= d; c *= Inv(m1, m2);//Inv为乘法逆元,数论常用内容——欧几里得算法与扩展欧几里得算法c %= m2; c *= m1 * d; c += a1; m3 = m1 * m2 * d; a3 = (c % m3 + m3) % m3; return true;
} LL CRT(LL a[], LL m[], int n) { LL a1 = a[1]; LL m1 = m[1]; for(int i=2; i<=n; i++) { LL a2 = a[i]; LL m2 = m[i]; LL m3, a3; if(!merge(a1, m1, a2, m2, a3, m3)) return -1; a1 = a3; m1 = m3; } return (a1 % m1 + m1) % m1;
}
参考:数论常用内容——中国剩余定理
下一篇:Codeforces Round 153 (Rated for Div. 2)
推荐音乐:沉沦于遐想
相关文章:
中国剩余定理及扩展
目录 中国剩余定理解释 中国剩余定理扩展——求解模数不互质情况下的线性方程组: 代码实现: 互质: 非互质: 中国剩余定理解释 在《孙子算经》中有这样一个问题:“今有物不知其数,三三数之剩二&#x…...
数据在内存中的存储(deeper)
数据在内存中的存储(deeper) 一.数据类型的详细介绍二.整形在内存中的存储三.浮点型在内存中的存储 一.数据类型的详细介绍 类型的意义: 使用这个类型开辟内存空间的大小(大小决定了使用范围)如何看待内存空间的视角…...
算法修炼Day52|● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组
LeetCode:300.最长递增子序列 300. 最长递增子序列 - 力扣(LeetCode) 1.思路 dp[i]的状态表示以nums[i]为结尾的最长递增子序列的个数。 dp[i]有很多个,选择其中最大的dp[i]Math.max(dp[j]1,dp[i]) 2.代码实现 1class Solution {2 pub…...
使用 HTML、CSS 和 JavaScript 创建实时 Web 编辑器
使用 HTML、CSS 和 JavaScript 创建实时 Web 编辑器 在本文中,我们将创建一个实时网页编辑器。这是一个 Web 应用程序,允许我们在网页上编写 HTML、CSS 和 JavaScript 代码并实时查看结果。这是学习 Web 开发和测试代码片段的绝佳工具。我们将使用ifram…...
百望云联合华为发布票财税链一体化数智解决方案 赋能企业数字化升级
随着数据跃升为数字经济关键生产要素,数据安全成为整个数字化建设的重中之重。为更好地帮助企业发展,中央及全国和地方政府相继出台了多部与数据相关的政策法规,鼓励各领域服务商提供具有自主创新的软件产品与服务,帮助企业在合规…...
实现两个栈模拟队列
实现两个栈模拟队列 思路:可以想象一下左手和右手,两个栈:stack1(数据所在的栈) ,stack2(临时存放)。 入队:需要将入队 num 加在 stack1 的栈顶即可; 出队&am…...
无涯教程-TensorFlow - 单词嵌入
Word embedding是从离散对象(如单词)映射到向量和实数的概念,可将离散的输入对象有效地转换为有用的向量。 Word embedding的输入如下所示: blue: (0.01359, 0.00075997, 0.24608, ..., -0.2524, 1.0048, 0.06259) blues: (0.01396, 0.11887, -0.48963, ..., 0.03…...
Facebook AI mBART:巴别塔的硅解
2018年,谷歌发布了BERT(来自transformers的双向编码器表示),这是一种预训练的语言模型,在一系列自然语言处理(NLP)任务中对SOTA结果进行评分,并彻底改变了研究领域。类似的基于变压器…...
BDA初级分析——SQL清洗和整理数据
一、数据处理 数据处理之类型转换 字符格式与数值格式存储的数据,同样是进行大小排序, 会有什么区别? 以rev为例,看看字符格式与数值格式存储时,排序会有什么区别? 用cast as转换为字符后进行排序 SEL…...
汽车后视镜反射率测定仪
后视镜是驾驶员坐在驾驶室座位上直接获取汽车后方、侧方和下方等外部信息的工具。它起着“第三只眼睛”的作用。后视镜按安装位置划分通常分为车外后视镜、监视镜和内后视镜。外后视镜观察汽车后侧方监视镜观察汽车前下方内后视镜观察汽车后方及车内情况。用途不一样镜面结构也…...
Redis学习笔记
redis相关内容 默认端口6379 默认16个数据库,初始默认使用0号库 使用select 切换数据库 统一密码管理,所有库密码相同 dbsize:查看当前库key的数量 flushdb:清空当前库 flushall:清空全部库 redis是单线程 多路…...
韩顺平Linux 四十四--
四十四、rwx权限 权限的基本介绍 输入指令 ls -l 显示的内容如下 -rwxrw-r-- 1 root 1213 Feb 2 09:39 abc0-9位说明 第0位确定文件类型(d , - , l , c , b) l 是链接,相当于 windows 的快捷方式- 代表是文件是普通文件d 是目录,相…...
【支付宝小程序】分包优化教程
🦖我是Sam9029,一个前端 Sam9029的CSDN博客主页:Sam9029的博客_CSDN博客-JS学习,CSS学习,Vue-2领域博主 🐱🐉🐱🐉恭喜你,若此文你认为写的不错,不要吝啬你的赞扬,求收…...
语言基础2 矩阵和数组
语言基础2 矩阵和数组 矩阵和数组是matlab中信息和数据的基本表示形式 可以创建常用的数组和网格 合并现有的数组 操作数组的形状和内容 以及使用索引访问数组元素 用到的函数列表如下 一 创建 串联和扩展矩阵 矩阵时按行和列排列的数据元素的二维数据元素的二维矩…...
springMVC中过滤器抛出异常,自定义异常捕获
在过滤器中引入org.springframework.web.servlet.HandlerExceptionResolver AutowiredQualifier("handlerExceptionResolver")private HandlerExceptionResolver resolver; // doFilter中处理if (条件1) {if (条件2) {resolver.resolveException(request, response, …...
图像检索技术研究:深度度量与深度散列在相似性学习中的应用比较与实践 - 使用Python与Jupyter环境
引言 在计算机视觉领域,图像检索是一个长期存在并持续受到研究者关注的重要话题。随着大数据时代的到来,如何高效、准确地从海量数据中检索到相似的图像成为一个巨大的挑战。传统的检索方法在大数据环境下表现不佳,而深度学习技术的崛起为图…...
CSS加载失败的6个原因
有很多刚刚接触 CSS 的新手有时会遇到 CSS 加载失败这个问题,但测试时,网页上没有显示该样式的问题,这就说明 CSS 加载失败了。出现这种状况一般是因为的 CSS 路径书写错,或者是在浏览器中禁止掉了 CSS 的加载,可以重新…...
react之路由的安装与使用
一、路由安装 路由官网2021.11月初,react-router 更新到 v6 版本。使用最广泛的 v5 版本的使用 npm i react-router-dom5.3.0二、路由使用 2.1 路由的简单使用 第一步 在根目录下 创建 views 文件夹 ,用于放置路由页面 films.js示例代码 export default functio…...
基于RoCE的应用程序的MTU注意事项
目录 基于RoCE的应用程序的MTU注意事项 探测网络中的MTU设置 概要 原文 MTU测试结果 DOC: CentOS安装tshark抓包工具 基于RoCE的应用程序的MTU注意事项 原文:https://support.mellanox.com/s/article/MLNX2-117-1682kn InfiniBand协议最大传输单元ÿ…...
springboot集成Graphql相关问题汇总
1、idea在debug运行时出现java.lang.NoClassDefFoundError:kotlin/collections/AbstractMutableMap 解决:禁用idea dubugger中kotlin coroutine agent 见:https://stackoverflow.com/questions/70796177/after-the-spring-boot-source-code-is-compile…...
Angular16的路由守卫基础使用
Angular16的路由守卫基础使用 使用ng generate guard /guard/login命令生成guard文件因新版Angular取消了CanActivate的使用,改用CanActivateFn,因此使用router跳转需要通过inject的方式导入。 import { inject } from angular/core; import { CanActi…...
leetcode228. 汇总区间
题目 给定一个 无重复元素 的 有序 整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中的每个区间范围 [a,b]…...
删除有序链表中重复的元素-II(链表)
乌!蒙!山!连!着!山!外!山! 题目: 思路: 双指针,slow和fast,并且增加标记flag初始为1。 如果slow指向节点值等于fast指向节点值&…...
element单独检验form表单中的一项
<el-form-item prop"limitDays" style"margin-left: 5px;"><el-input v-model"ruleForm.limitDays" placeholder"天数" style"width: 100px;" /> </el-form-item> <el-form-item prop"limitCount…...
Webpack node、output.jsonpFunction 配置详解
Webpack node、output.jsonpFunction 配置详解 最近尝试给一些用到 webpack 的项目升级到最新 webpack5 版本,其中遇到了一些问题,我挑了两个比较典型的问题,其中主要涉及到了 webpack 的 node 属性跟 output.jsonpFunction (web…...
要跟静音开关说再见了!iPhone15新变革,Action按钮引领方向
有很多传言称iPhone 15 Pro会有很多变化,但其中一个变化可能意味着iPhone体验从第一天起就有的一项功能的终结。我说的是静音开关,它可以让你轻松地打开或关闭iPhone的铃声。 根据越来越多的传言,iPhone 15 Pro和iPhone 15 Pro Max将拆除静音…...
论文笔记 Graph Attention Networks
2018 ICLR 1 intro 1.1. GCN的不足 无法完成inductive任务 inductive任务是指: 训练阶段与测试阶段需要处理的graph不同。通常是训练阶段只是在子图上进行,测试阶段需要处理未知的顶点。GGN 的参数依赖于邻接矩阵A/拉普拉斯矩阵L,所以换了…...
看上去就很像的agree和degree有什么联系
“Agree”(同意)和 “degree”(程度)这两个词在语义上没有直接的联系,它们代表不同的概念。 “Agree” 意味着在意见、观点或立场上达成共识或一致。它表示同意或同意某人或某事。 例如: “We all agree…...
2023前端面试题第二弹(真实,一般人我还不给看)
为什么要初始化css? 避免浏览器差异,解决兼容问题 网格布局 display: grid; grid-template-columns: 1fr 1fr 1fr less的优点 可以兼容,可以嵌套,循环,运算,定义变量和继承样式(extendÿ…...
零基础如何学习 Web 安全,如何让普通人快速入门网络安全?
前言 网络安全现在是朝阳行业,缺口是很大。不过网络安全行业就是需要技术很多的人达不到企业要求才导致人才缺口大 【一一帮助安全学习(网络安全面试题学习路线视频教程工具)一一】 初级的现在有很多的运维人员转网络安全,初级…...
安全学习DAY18_信息打点-APP资产搜集
信息打点-APP资产&静态提取&动态抓包&动态调试 文章目录 信息打点-APP资产&静态提取&动态抓包&动态调试本节知识&思维导图本节使用到的链接&工具 如何获取目标APP从名称中获取APP从URL获取APP APP搜集资产信息APP提取信息分类信息提取方式信息…...
react 矩形波浪
"矩形波浪"(Square Wave)在信号处理和波形生成中是一种特殊类型的波形,通常由两个不同的值交替组成,一个是高电平,另一个是低电平,形成类似方波的波形。在 React 中创建一个矩形波浪的效果可以通…...
【GitHub】Pycharm本地项目打包上传到Github仓库的操作步骤
文章目录 1、Pycharm端的设置操作2、Github端的设置操作3、Pycharm上配置Github4、Git本地项目至GitHub仓库5、前往Github中查看确认6、常见报错 1、Pycharm端的设置操作 通过CtrlAltS快捷组合键的方式,打开设置,导航到版本控制一栏中的Git,…...
计算机网络基础
前言 在你立足处深挖下去,就会有泉水涌出!别管蒙昧者们叫嚷:“下边永远是地狱!” 博客主页:KC老衲爱尼姑的博客主页 博主的github,平常所写代码皆在于此 共勉:talk is cheap, show me the code 作者是爪哇岛的新手,水平很有限&…...
【图像分类】基于LIME的CNN 图像分类研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
回归预测 | MATLAB实现TSO-SVM金枪鱼群算法优化支持向量机多输入单输出回归预测(多指标,多图)
回归预测 | MATLAB实现TSO-SVM金枪鱼群算法优化支持向量机多输入单输出回归预测(多指标,多图) 目录 回归预测 | MATLAB实现TSO-SVM金枪鱼群算法优化支持向量机多输入单输出回归预测(多指标,多图)效果一览基…...
Pixar、Adobe 和苹果等成立 OpenUSD 联盟推行 3D 内容开放标准
导读Pixar、Adobe、Apple、Autodesk 与 NVIDIA 联手 Linux 基金会旗下的联合开发基金会(JDF)宣布建立 OpenUSD 联盟(AOUSD)以推行 Pixar 创建的通用场景描述技术的标准化、开发、进化和发展。 联盟寻求通过推进开放式通用场景描述…...
ansible剧本之role角色模块
role角色 一:Roles 模块1.roles 的目录结构:2.roles 内各目录含义解释3.在一个 playbook 中使用 roles 的步骤:(1)创建以 roles 命名的目录(2)创建全局变量目录(可选)&am…...
网络安全领域的常见攻击方式及防御手段
目录 重放攻击(Replay Attack)防御手段 SQL 注入(SQL Injection)防御手段 跨站脚本攻击(Cross-Site Scripting,XSS)防御手段 跨站请求伪造(Cross-Site Request Forgery,C…...
Python应用工具-Jupyter Notebook
工具简介 Jupyter Notebook是 基于 网页的用于交互计算的 应用程序,以网页的形式打开,可以在网页页面中直接编写代码和运行代码,代码的运行结果也会直接在代码块下 显示,文档是保存为后缀名为 . ipynb 的 JSON 格式文件。 操作指令…...
音视频 FFmpeg如何查询命令帮助文档
FFmpeg如何查询命令帮助文档 一、ffmpeg/ffplay/ffprobe区别二、ffmpeg命令查看帮助文档三、ffplay命令查看帮助文档四、ffprobe命令查看帮助文档注意 一、ffmpeg/ffplay/ffprobe区别 ffmpeg:超快音视频编码器ffplay:简单媒体播放器ffprobe:简单多媒体流分析器 二、ffmpeg命令…...
回归预测 | MATLAB实现CSO-SVM布谷鸟优化算法优化支持向量机多输入单输出回归预测(多指标,多图)
回归预测 | MATLAB实现CSO-SVM布谷鸟优化算法优化支持向量机多输入单输出回归预测(多指标,多图) 目录 回归预测 | MATLAB实现CSO-SVM布谷鸟优化算法优化支持向量机多输入单输出回归预测(多指标,多图)效果一…...
元宇宙电商—NFG系统:区块链技术助力商品确权。
在国内,以“数字藏品”之名崛起以来,其与NFT的对比就从未停歇。从上链模式到数据主权,从炒作需求到实际应用,从售卖形式到价值属性,在各种抽丝剥茧般的比较中,围绕两者孰优孰劣的讨论不绝于耳。 NFT的每一…...
【云原生】Docker基本原理及镜像管理
目录 一、Docker概述 1.1 IT架构的演进: 1.2 Docker初始 1.3 容器的特点 1.4 Docker容器与虚拟机的区别 1.5 容器在内核中支持2种重要技术 1.6 Docker核心概念 1)镜像 2)容器 3)仓库 二、安装Docker 2.1 Yum安装Docker…...
Apache Doris大规模数据使用指南
目录 发展历史 架构介绍 弹性MPP架构-极简架构 逻辑架构 基本访问架构 分区 创建单分区表...
RabbitMQ 持久化
通过持久化可以尽量防止在RabbitMQ异常情况下(重启、关闭、宕机)的数据丢失。持久化技术是解决消息存储到队列后的丢失问题,但是通过持久化并不能完全保证消息不丢失。 持久化 交换机持久化队列持久化消息持久化总结 持久化技术可以分为交换机…...
STM32 定时器复习
12MHz晶振的机器周期是1us,因为单片机的一个机器周期由6个状态周期组成,1个机器周期6个状态周期12个时钟周期,因此机器周期为1us。 51单片机常用 for(){__nop(); //执行一个机器周期,若想循环n us,则循环n次。 }软件…...
17-工程化开发 脚手架 Vue CLI
开发Vue的两种方式: 1.核心包传统开发模式: 基于 html/css /js 文件,直接引入核心包,开发 Vue。 2.工程化开发模式: 基于构建工具 (例如: webpack)的环境中开发 Vue。 问题: 1. webpack 配置不简单 2. 雷同的基础配置 3. 缺乏统…...
golang 分布式微服务DAO层构建
构建云原生项目的dao层 配置读写分离的mysql集群 1. 编写yml配置文件 搭建一主二从的mysql集群、单机redis db.yml mysql:source: # 主数据库driverName: mysqlhost: 127.0.0.1port: 3309database: db_tiktokusername: tiktokDBpassword: tiktokDBcharset: utf8mb4replica1…...
Java 项目日志实例:LogBack
点击下方关注我,然后右上角点击...“设为星标”,就能第一时间收到更新推送啦~~~ LogBack 和 Log4j 都是开源日记工具库,LogBack 是 Log4j 的改良版本,比 Log4j 拥有更多的特性,同时也带来很大性能提升。LogBack 官方建…...