python实现中国剩余定理

中国剩余定理又称孙子定理,是数论中一个重要定理。最早可见于我国的数学著作《孙子算经》卷下“物不知数”问题,原文如下:

有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?即,一个整数除以三余二,除以五余三,除以七余二,求这个整数。

把这题转化成现代数学问题:

求一个数x,该数除以3余2,除以5余3,除以7余2

把以上问题转化为一般方程的形式

根据中国剩余定理解如下

其中

python代码实现

n = int(input())
b = list(map(int, input().split()))  # 余数
m = list(map(int, input().split()))  # 模数
M = [0] * n
m_total = 1
x = 0  # 解,初始化为0
for i in range(n):
    m_total *= m[i]  # 计算m_total

for i in range(n):
    M[i] = m_total // m[i]  # 计算M[i]

for i in range(n):
    x += b[i] * M[i] * pow(M[i], -1, m[i])  # pow(M[i], -1, m[i])表示M[i]模m[i]的逆元
print(x % m_total)  # 该解有无数个,取一个模m_total的最小正整数解

第一行输入有几个方程

第二行输入每个方程的余数

第三行输入每个方程的模数

如一开始《孙子算经》的那题输入

3
2 3 2
3 5 7

结果为

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/377245.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

一步步建立一个C#项目(连续读取S7-1200PLC数据)

这篇博客作为C#的基础系列,和大家分享如何一步步建立一个C#项目完成对S7-1200PLC数据的连续读取。首先创建一个窗体应用。 1、窗体应用 2、配置存储位置 3、选择框架 拖拽一个Button,可以选择视图菜单---工具箱 4、工具箱 拖拽Lable控件和TextBook控件 5、拖拽控件 接下来…

Linux文件和目录管理

目录基础 Linux操作系统以目录的方式来组织和管理系统中的所有文件。所谓的目录,就是将所有文件的说明信息采用树状结构组织起来。每个目录节点之下会有文件和子目录。 所有一切都从 ‘根’ 开始,用 ‘/’ 代表, 并且延伸到子目录。 bin:B…

《MySQL 简易速速上手小册》第2章:数据库设计最佳实践(2024 最新版)

文章目录 2.1 规划高效的数据库架构2.1.1 基础知识2.1.2 重点案例2.1.3 拓展案例 2.2 数据类型和表设计2.2.1 基础知识2.2.2 重点案例2.2.3 拓展案例 2.3 索引设计原则2.3.1 基础知识2.3.2 重点案例2.3.3 拓展案例 2.1 规划高效的数据库架构 在开启我们的数据库设计之旅之前&a…

240207-3步设置VSCode插件Inline-Bookmarks自定义颜色及名称

Step 1: 插件安装 Step 2: 配置文件 "inline-bookmarks.expert.custom.styles": {"default": {"gutterIconColor": "#157EFB","overviewRulerColor": "rgba(21, 126, 251, 0.7)","light": {"fontW…

【C++从0到王者】第四十二站:类型转换

文章目录 一、 C语言中的类型转换1. C语言中的类型转换2.一个常见的坑 二、为什么C需要四种类型转换三、C强制类型转换1.static_cast2.reinterpret_cast3.const_cast4.dynamic_cast 四、RTTI 一、 C语言中的类型转换 1. C语言中的类型转换 在C语言中,如果赋值运算符…

MOS管防反接电路设计

电子元件大都是使用直流工作,电源线反接就有可能就会烧坏,那电路如何防反接?首当其冲我们想到的就是二极管了,运用其单向导通特性可有效防止电源反接而损坏电路,但是随之而来的问题是二极管存在PN节电压,通…

【C++航海王:追寻罗杰的编程之路】类与对象你学会了吗?(下)

目录 1 -> 再谈构造函数1.1 -> 构造函数体赋值1.2 -> 初始化列表1.3 -> explicit关键字 2 -> static成员2.1 -> 概念2.2 -> 特性 3 -> 友元3.1 -> 友元函数3.2 -> 友元类 4 -> 内部类5 -> 匿名对象6 -> 拷贝对象时的一些编译器优化 1 -…

Three.js学习7:dat.GUI 参数控制

每个学 Three.js 的都被安利了 dat.GUI 吧? 我也不例外! 今天就来了学习下 dat.GUI,并记录下来自己的学习成果。 一、什么是 dat.GUI? dat.GUI 是一个轻量级的图形用户界面库(GUI 组件),使用这个库可以…

进程状态 | 僵尸进程 | 孤儿进程 | 前台后台进程 | 守护进程

文章目录 1.进程的三种基本状态2.Linux中进程状态查看2.1.进程检测脚本2.2.各种状态查看 3.孤儿进程4.前台、后台、守护进程 1.进程的三种基本状态 进程的在系统当中是走走停停的,「运行 - 暂停 - 运行」的活动规律;进程在活动期间的三种状态&#xff1…

还得是它!GPT4.0和MJ都搞定了!SD也快了!

之前给大家分享过一个国内的AI镜像平台——葫芦AI,目前接入了Midjourney和DALL3、GPT4.0和文心一言4.0。 前几天夜里1点多这个葫芦AI台平‬升级了GPT4接口和资料库,立试马‬用了‬一下,很‬不错。接口‬能力和官‬方差‬不多。后面能把Gpts和…

新增C++max函数的使用

在 C 中&#xff0c;max函数是标准库中的一个函数&#xff0c;用于返回两个或多个元素中的最大值。max函数的声明如下&#xff1a; cpp #include <algorithm>template<class T> const T& max(const T& a, const T& b);这个函数接受两个同类型的参数a…

部署一个在线OCR工具

效果 安装 1.拉取镜像 # 从 dockerhub pull docker pull mmmz/trwebocr:latest 2.运行容器 # 运行镜像 docker run -itd --rm -p 10058:8089 --name trwebocr mmmz/trwebocr:latest 使用 打开浏览器输入 http://192.168.168.110:10058/ 愉快滴使用吧

【开源】基于JAVA+Vue+SpringBoot的贫困地区人口信息管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 人口信息管理模块2.2 精准扶贫管理模块2.3 特殊群体管理模块2.4 案件信息管理模块2.5 物资补助模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 人口表3.2.2 扶贫表3.2.3 特殊群体表3.2.4 案件表3.2.5 物资补助表 四…

肯尼斯·里科《C和指针》第12章 使用结构和指针(2)双链表

12.3 双链表 单链表的替代方案就是双链表。在一个双链表中&#xff0c;每个节点都包含两个指针——指向前一个节点的指针和指向后一个节点的指针。这可以使我们以任何方向遍历双链表&#xff0c;甚至可以随意在双链表中访问。下面的图展示了一个双链表。 下面是节点类型的声明&…

为什么大模型需要向量数据库?

AIGC 时代万物都可以向量化&#xff0c;向量化是 LLM 大模型以及 Agent 应用的基础。 比如&#xff1a;爆火的 Google 大模型 Gemini 1.0 原生支持的多模态&#xff0c;在预训练的时候就是把文本、图片、音频、视频等多模态先进行 token 化&#xff0c;然后构建一维的“语言”…

Powershell Install 一键部署Openssl+certificate证书创建

前言 Openssl 是一个方便的实用程序,用于创建自签名证书。您可以在所有操作系统(如 Windows、MAC 和 Linux 版本)上使用 OpenSSL。 Windows openssl 下载 前提条件 开启wmi,配置网卡,参考 自签名证书 创建我们自己的根 CA 证书和 CA 私钥(我们自己充当 CA)创建服务器…

数据结构第九天(堆排序)

目录 前言 概述 源码&#xff1a; 主函数&#xff1a; 运行结果&#xff1a; 其他 前言 哈哈&#xff0c;这个堆排序算法很久之前就已经敲过一遍了&#xff0c;时间一久&#xff0c;思路有点淡忘。今天重新看过一遍之后&#xff0c;又亲自撸代码&#xff0c;幸运的是&am…

【RL】Bellman Equation (贝尔曼等式)

Lecture2: Bellman Equation State value 考虑grid-world的单步过程&#xff1a; S t → A t R t 1 , S t 1 S_t \xrightarrow[]{A_t} R_{t 1}, S_{t 1} St​At​ ​Rt1​,St1​ t t t, t 1 t 1 t1&#xff1a;时间戳 S t S_t St​&#xff1a;时间 t t t时所处的sta…

C++ | vector二维数组的初始化与行、列数的获取

如果直接使用vector<int,vector<int> > v;创建二维数组&#xff0c;那么就会得到一个空的容器&#xff0c;这样再通过push_back赋值是非常麻烦的。 初始化二维数组 在此介绍二维数组初始化的一般操作。 首先看一维数组的初始化示例&#xff1a; 定义一个长度为n&a…

拿捏循环链表

目录&#xff1a; 一&#xff1a;单链表&#xff08;不带头单向不循环&#xff09;与循环链表&#xff08;带头双向循环&#xff09;区别 二&#xff1a;循环链表初始化 三&#xff1a;循环链表头插 四&#xff1a;循环链表尾插 五&#xff1a;循环链表头删 六&#xff1…