模数非互质的同余方程组(非互质版中国剩余定理)_中国剩余定理模数不互质怎么求-程序员宅基地

技术标签: 算法  

之前介绍到的中国剩余定理只能求解模数两两互质的同余方程组。

   那么,模数如果不一定两两互质的情况应该怎么求呢?

   下面介绍通过合并方程的方法来解决问题(要用到扩展欧几里德算法)。

 

   顾名思义,合并方程就是把所有的同余方程组合并成一个。

   举个例子,合并同余方程组  x%A=a  

                              x%B=b       

   现在给出两种合并的方法:

    1)要把①②式合并成    x%C=c   

       易知C一定是A和B的最小公倍数的倍数,否则不可能同时满足①②两式。

       这里我们取C为A,B的最小公倍数,设d=gcd(A,B),则C=A*B/d.

       接下来我们只要求出余数c即可,假设p是方程组①②的其中一个解

       因为③是①②两式的合并方程,所以p也是③的解,所以可以得到c=p%C

       接下来的问题就是怎么求出方程组①②的其中一个解。

       首先,满足方程组①的最小解显然就是x=a

       然后满足①②的解就是 (a+kA)%B=b,其中x=a+kA(k为任意自然数)

       这个方程很明显可以用扩展欧几里德算法即可求得x,这样就完成了两个方程的合并

       

       当所有的同余方程合并成一个方程 x%G=g 时候,g即为最终的最小解。。

  

   2)至于第二种方法,请参考http://972169909-qq-com.iteye.com/blog/1266328

      这种方法我也不是太了解,日后会完善。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/onestow/article/details/9673741

智能推荐

json_encode 和 serialize(一)_serialize 和json_encode-程序员宅基地

文章浏览阅读3.6k次。今天在看书的时候(作为一个菜鸟,看书是必须滴 嘿嘿),看到了序列化,php的序列化一般使用serialize和json_encode,按照之前的学习方法,我可能就只会把这个两个函数的用法区别搞清楚下就pass继续看其他内容了,但是之前在csdn博客上看到李运华老师的博客再结合平时师傅提醒的学习方法,感觉之前的老方法不是一个合格的程序员应该做的,作为一个程序员,合格的程序员应该善于挖掘(师傅说的),_serialize 和json_encode

修改profile文件时提示只读的解决办法-程序员宅基地

文章浏览阅读1.1w次,点赞3次,收藏9次。3、A:linux恢复模式下修改profile文件报只读错误 安了个ubuntu,今天装了个JDK环境,配置环境变量时,我修改的是/etc/profile文件,但被我改错了,把PATH那个环境变量改错了,..._profile只读

Halcon学习笔记----region_to_bin算子详解-程序员宅基地

文章浏览阅读9.4k次,点赞3次,收藏16次。今天终于解决了困扰我很久的一个问题,在VC中调用HALCON中的分割函数后,在最后返回显示时总是报错,让我郁闷了很久,Undefined gray in get_image_pointer3 或Undefined gray in get_image_pointer。 原来问题出在对于bin_threshold、threshold等这些分割函数的返回值上面,把返回值当成Imag_region_to_bin

微信公众号开发之获得素材列表_csdn服务商获取公众号素材-程序员宅基地

文章浏览阅读1k次。微信公众号开发之获得素材列表对于获得公众号的素材列表首先需要阅读微信开发者手册开发准备工具测试公众号内网穿透HTTP地址(微信对本地服务的通信对一些,公众号信息的获取不需要)具体参考:https://developers.weixin.qq.com/doc/offiaccount/Getting_Started/Overview.html[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QgOcoCTL-1625189967278)(C:\Users\wang\Ap_csdn服务商获取公众号素材

使用rz命令从本地上传文件到linux服务器卡住问题_putty rz上传文件没反应-程序员宅基地

文章浏览阅读3.2k次。问题背景:使用putty进行ssh远程连接,上传文件时选用sz命令,但是一执行这个命令,终端就会被卡着。解决办法:换成使用xshell连接远程服务器,或者其他支持lrzsz上传服务的软件。lrzsz:本地和服务器的文件互传工具下载安装方式:yum -y install lrzsz当然也可以使用wget方式,只不过有点麻烦。命令解析:rz (receive)从本地上传到远程服务sz (send)从远程服务到本地..._putty rz上传文件没反应

Android7.0 IMS(1)开机初始化_android监听imsmanager初始化状态-程序员宅基地

文章浏览阅读9.2k次。IMS(IP Multimedia Subsystem)被认为是下一代网络的核心技术,是解决移动与固网融合,引入语音、数据、视频三重融合等差异化业务的重要方式。Android作为移动网络终端的主要操作系统,也提供了对IMS的支持。 本篇博客的目的就是弄清楚Android中的IMS是如何完成开机初始化的。_android监听imsmanager初始化状态

随便推点

一文读懂索引(覆盖索引,最左匹配原则)_覆盖索引 a,b,c a = 1 and b > 1 and c = 1 走索引吗, a = 1 a-程序员宅基地

文章浏览阅读3.8k次,点赞9次,收藏11次。1. 什么是索引索引是帮助数据库高效获取数据的数据结构。简而言之,索引是数据结构2. 索引的底层数据结构2.1 Hash索引哈希表是键值对的集合,通过键(key)即可快速取出对应的值(value),因此哈希表可以快速检索数据(接近 O(1))。为何能够通过 key 快速取出 value呢? 原因在于 哈希算法(也叫散列算法)。通过哈希算法,我们可以快速找到 value 对应的 index,找到了 index 也就找到了对应的 value。index = hash % array.size()_覆盖索引 a,b,c a = 1 and b > 1 and c = 1 走索引吗, a = 1 and b = 1 and c

用java构建企业级自动化框架(首篇-制定测试者使用语言3)_eclipse自动化用企业级的吗-程序员宅基地

文章浏览阅读786次。接下来对数据库的测试也提供一种编写思路,具体如何实现这个就不细说了。 testjingdongcom.productId">SELECT DISTINCT p.po_no FROM wff_po_line p, wff_line_item l WHERE p.co_order_no=[orderNo]AND l.order_no = p.co_order_no_eclipse自动化用企业级的吗

云原生|容器和应用安全运营实践思考-程序员宅基地

文章浏览阅读1.8k次。文| 腾讯“洋葱”入侵对抗团队bghost前言随着云计算的蓬勃发展,云原生概念被提出并快速发展,公司内部也在推进使用云原生技术进行架构优化,研发模式和基础设施都发生了很大的变化,新的k8s..._腾讯云部署容器安全 操作

exception is org.springframework.beans.factory.NoUniqueBeanDefinitionException-程序员宅基地

文章浏览阅读2.1k次。spring_org.springframework.beans.factory.nouniquebeandefinitionexception

conda新建环境时报错NotWritableError: The current user does not have write permissions_environmentnotwritableerror: the current user does-程序员宅基地

文章浏览阅读4.9k次,点赞5次,收藏20次。目录1、问题描述2、问题原因3、解决方案4、测试5、参考自1、问题描述在使用conda create -n environment_name命令新建环境时,遇到错误:Solving environment: failedNotWritableError: The currenuser does not have write permissions to a required path. path: /home/user_name/.conda/pkgs/u.._environmentnotwritableerror: the current user does not have write permission

Zeppelin的Tableau可视化结果的优化小技巧(四)_tableau时间坐标轴顺序-程序员宅基地

文章浏览阅读171次。文章目录在折线图末尾添加自定义图形以增加美感制作方法追记在折线图末尾添加自定义图形以增加美感本期博客将继续为大家介绍一个Tableau的可视化结果的优化技巧,即在折线图的末尾处添加自定义图形用以增加整体美感。(注:此次演示只介绍了技巧,并未真正使用自定义图形,因此美感提升有限,望各位海涵)本次可视化所使用的数据依然来自开源的OECD Data。制作方法我们将以如下简单的折线图开始,完成自定义图形的追加。首先我们观察到折线图本身下方留白较多,因此推荐通过取消显示原点来更好地反应折线的起伏。_tableau时间坐标轴顺序

推荐文章

热门文章

相关标签