中国剩余定理(孙子定理)的证明和c++求解
《孙子算经》里面的"物不知数"说的是这样的一个题目：一堆东西不知道具体数目，3个一数剩2个，5个一数剩3个，7个一数剩2个，问一共有多少个。
书里面给了计算过程及答案：70*2 + 21*3 + 15*2 -105*2 = 23。
它的计算思路如下：
70是能被5或7整除的数字，但是除以3正好余1。
21是能被3或7整除的数字，但是除以5正好余1。
15是能被3或5整除的数字，但是除以7正好余1。
所以若有数N = 70 * N1 + 21 * N2 + 15 * N3(其中N,N1,N2,N3为正整数)，则整数N是符合题目要求的结果(mod3为N1，mod5为N2， mod7为N3)。
我们把N1赋值2，N2赋值3，N3赋值2。
则: N = 70*2 + 21*3 + 15*2 = 233。
但是3，5，7的最小公倍数为105。
所以N + 105*M均为正解。
因此为了求得最小正整数解，我们需要用(N mod 105)也就是23了。
中国剩余定理(西方数学史中的叫法)，就是上一题目的一般情况。
设m1,m2...mk是两两互素的正整数，即: gcd(mi, mj) = 1 (其中 i != j, i, j >= 1且 <=k).
则同余方程组:
x ≡ a1(mod m1)
x ≡ a2(mod m2)
... ...
x ≡ ak(mod mk)
存在唯一[m1,m2...mk]使方程成立.
解法同物不知数是一致的.我们可以稍微模仿一下.
唯一的难题就是如何把上面70, 15, 21的求法,对应到一般情况来.
假设: N1, N2, ... ,Nk.就是对应的权值, 满足如下条件:
N1 能够被 m2, m3..., mk整除,但是除以m1正好余1.
N2 能够被 m1, m3..., mk整除,但是除以m2正好余1.
... ...
Nk能够被m1, m2,...,mk-1整除,但是除以mk正好余1.
N1->Nk如果求出来了,那么假设:
x1 = N1*a1 + N2*a2 + ... + Nk*ak就是我们要求的x一个解, 同物不知数一样,我们把x1 mod (m1*m2*...*mk)的结果
就是x的最小整数解,若为负数,则再加上一个m1*m2*...*mk.因为加减整数倍个m1*m2*...*mk所得结果都是x的解.
所以问题只剩下一个,就是求N1, N2,...,Nk.
怎么求呢?我需要先化简一番:
设m = m1*m2*...*mk, L, J为任意整数.
因为Ni能被m1, m2,...,mi-1, mi+1,...,mk整除(其中i+1<k)
因此: Ni = m/mi *L
| 扩展欧几里德定理： a和b都是不全为0的正整数，则： a*x + b*y = gcd(a, b) 存在唯一的x, y使得上面等式成立。 (当然，容易得知，如果，a和b中有负数，那么也是成立的。) 本题中，m/mi相当于a, -mi相当于b, L相当于x, J相当于y。求出L, J就能求出Ni。 |
代码:
#include <iostream>
using namespace std;
//参数可为负数的扩展欧几里德定理
void exOJLD(int a, int b, int &x, int &y){//根据欧几里德定理if(b == 0){//任意数与0的最大公约数为其本身。x = 1;y = 0;}else{int x1, y1;exOJLD(b, a%b, x1, y1);if(a*b < 0){//异号取反x = - y1;y = a/b*y1 - x1;}else{//同号x = y1;y = x1 - a/b* y1;}}
}
//剩余定理
int calSYDL(int a[], int m[], int k){int N[k];//这个可以删除int mm = 1;//最小公倍数int result = 0;for(int i = 0; i < k; i++){mm *= m[i];}for(int j = 0; j < k; j++){int L, J;exOJLD(mm/m[j], -m[j], L, J);N[j] = m[j] * J + 1;//1N[j] = mm/m[j] * L;//2 【注】1和2这两个值应该是相等的。result += N[j]*a[j];}return (result % mm + mm) % mm;//落在(0, mm)之间，这么写是为了防止result初始为负数，本例中不可能为负可以直接 写成：return result%mm;即可。
}int main(){int a[3] = {2, 3, 2};int m[3] = {3, 5, 7}; cout<<"结果:"<<calSYDL(a, m, 3)<<endl;
}相关文章：
osi七层网络层_OSI层速成课程
osi七层网络层介绍 (Introduction) Have you ever wondered how data is sent through the network from one machine to another? If yes, then the Open System Interconnected model is what you are looking for.您是否曾经想过如何通过网络将数据从一台机器发送到另一台机…
KMP算法求回溯数组的步骤
KMP算法到底是什么原理就不说了，各种资料上讲的明明白白，下面我就如何用代码来实现做一下说明和记录. KMP的核心思想就是，主串不回溯，只模式串回溯。而模式串匹配到第几位时失配，要回溯多少，由模式串本身来…
【.Net】vs2017 自带发布工具 ClickOnce发布包遇到的问题
一、遇到的问题 在安装了vs2017 社区版（Community）之后 想打包安装程序（winform） 还是想用之前的 installshield来打包 发现居然打不了，在官网查了 installshield不支持社区版（Community）&…
windows平台，开发环境变量配置
1.打开我的电脑--属性--高级--环境变量 JAVA配置环境变量变量名：JAVA_HOME 变量值：C:\Program Files\Java\jdk1.7.0 变量名：CLASSPATH 变量值：.;%JAVA_HOME%\lib\dt.jar;%JAVA_HOME%\lib\tools.jar; 变量名：Path 变…
如何编写可测试的代码 哈利勒的方法论
Understanding how to write testable code is one of the biggest frustrations I had when I finished school and started working at my first real-world job. 当我完成学业并开始从事第一份现实世界的工作时，了解如何编写可测试的代码是我最大的挫败之一。 T…
【Java入门提高篇】Day6 Java内部类——成员内部类
内部类是什么，简单来说，就是定义在类内部的类（一本正经的说着废话）。 一个正经的内部类是长这样的： public class Outer {class Inner{} } 这是为了演示而写的类，没有什么luan用，可以看到Inner类…
POJ 1001(高精度乘法 java的2种解法)
方法1: import java.math.BigDecimal; import java.util.Scanner; public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);while(sc.hasNext()){String d sc.next();int z sc.nextInt();BigDecimal bd new BigDecimal(d);BigDeci…
Java编写的电梯模拟系统《结对作业》
作业代码：https://coding.net/u/liyi175/p/Dianti/git 伙伴成员：李伊 http://home.cnblogs.com/u/Yililove/ 对于这次作业，我刚开始一点思绪都没有，在老师安排了结对伙伴李伊之后，我的搭档问我，我们需要什么…
HTML属性说明
HTML elements can have attributes, which contain additional information about the element.HTML元素可以具有属性，其中包含有关该元素的其他信息。 HTML attributes generally come in name-value pairs, and always go in the opening tag of an element. Th…
css中的选择器
1.在html中引入css的方法：四种方式: a.行内式(也称内联式) 如: <h1 style"color:red;test</h1> b.内嵌式 <style type"text/css"> h1{ color:red; font-size: 10.5pt; font-family: Calibri, sans-serif; line-height: normal; widow…
javascript的call()方法与apply()方法的理解
先看一段代码 function cat() {} cat.prototype{food:fish,say:function () {console.log(I love this.food);} };var blackCat new cat(); blackCat.say(); 这时，控制台输出 I love fish若此时，有另一个对象 Dog{food:bones and shit}; dog对象没有say…
java排序算法(冒泡，插入，选择，快速，堆，归并，希尔，基数)
import java.util.Arrays; import java.util.LinkedList;/*** * * 各种排序: 冒泡，插入，选择，快速，堆，归并，希尔，基数*/ public class Sorts {//1. 冒泡：//时间复杂度:n(n-1)/2O(n^2…
边界填充算法讲解_边界填充算法
边界填充算法讲解Boundary fill is the algorithm used frequently in computer graphics to fill a desired color inside a closed polygon having the same boundary color for all of its sides.边界填充是在计算机图形学中经常使用的算法，用于在其所有边都具有…
使用Git管理源代码
git是个了不起但却复杂的源代码管理系统。它能支持复杂的任务，却因此经常被认为太过复杂而不适用于简单的日常工作。让我们诚实一记吧：Git是复杂的，我们不要装作它不是。但我仍然会试图教会你用（我的）基本的Git和远程代…
[.Net跨平台]部署DTCMS到Jexus遇到的问题及解决思路---Linux环境搭建
最近朋友托我帮忙研究如何把一个DTCMS部署到Linux下，经过1天的研究，部署基本成功，可能有些细节还未注意到，现在把心得分享一下。过程比预期的要简单 身为.Net程序员，这个问题的第一步可能就是如何搭建一个Linux环境来测…
Sequence point 中文
摘自维基百科： In C[4] and C,[5] sequence points occur in the following places. (In C, overloaded operators act like functions, and thus operators that have been overloaded introduce sequence points in the same way as function calls.) Between ev…
python中pop函数_Python中的Pop函数
python中pop函数什么是弹出功能？ (What is the pop function?) The method pop() removes and returns the last element from a list. There is an optional parameter which is the index of the element to be removed from the list. If no index is specified…
第六周学习进度条
日期 任务 听课 编程 阅读 准备考试 日总计 周日 周一 120 300 0 0 420 100 周二 0 120 0 0 120 周三 0 0 0 0 0 周四 0 0 0 0 0 周五 0 0 0 0 0 周六 0 120 100 0 …
1071. 小赌怡情(15)
常言道“小赌怡情”。这是一个很简单的小游戏：首先由计算机给出第一个整数；然后玩家下注赌第二个整数将会比第一个数大还是小；玩家下注t个筹码后，计算机给出第二个数。若玩家猜对了，则系统奖励玩家t个筹码；…
关于年长程序员的5个误传
原文链接：http://kb.cnblogs.com/page/150932/ 英文原文：Five Pervasive Myths About Older Software Developers 最近我刚过完40岁生日，一个朋友向我开玩笑地说“嘿，你已经老了，不适合做程序员了！”我虽然…
java中getter_Java中的Getter和Setters解释了
java中getterGetters and setters are used to protect your data, particularly when creating classes. Getter和Setter用于保护数据，尤其是在创建类时。 For each instance variable, a getter method returns its value while a setter method sets or updates…
Loadrunner手动关联详解
Loadrunner手动关联详解 一、关联的含义： 关联（correlation）：在脚本回放过程中，客户端发出请求，通过关联函数所定义的左右边界值（也就是关联规则），在服务器所响应的内容中…
解决Visual Studio禁止使用strlen函数的问题
问题描述： 在学习C的复制构造函数以及复制赋值运算符的重载时，需要用到使用C风格的字符串作为引入，由于我用的是VS2015（社区版），在编译时出错。编译器提醒strcpy函数是不安全的，建议改用strlen_…
求整型数组所有子串的和中的最大值
#include <iostream> using namespace std;const int MIN_INT -2147483647;int maxSum(const int *arr, int len){int my_max MIN_INT;int tmp 0;for(int i 0; i < len; i){//从头到尾。。tmp arr[i];//遍历相加。if(my_max < tmp){//更新my_maxmy_max tmp;}…
c语言中的if语句_If ... C中的其他语句解释
c语言中的if语句Conditional code flow is the ability to change the way a piece of code behaves based on certain conditions. In such situations you can use if statements.条件代码流是根据某些条件更改一段代码的行为的能力。 在这种情况下，可以使用if语句…
设计模式之笔记--装饰模式（Decorator）
装饰模式（Decorator） 定义 装饰模式（Decorator），动态地给一个对象添加一些额外的职责，就增加功能来说，装饰模式比生成子类更为灵活。 类图 描述 Component：被装饰者和装饰者共有的基…
整型数组负数放左面，其他放右面，要求时空复杂度:O(n), O(1)。
例如：处理前：{5 -3 6 -7 -6 1 8 -4 0 0}，处理后：{-3 -7 -6 -4 5 6 1 8 0 0}. #include <iostream> #include <algorithm> using namespace std;const int LEN 10; void printInt(int c){cout<<c<<"…
[bzoj] 1176 Mokia || CDQ分治
原题 给出WW的矩阵（S没有用，题目有误），给出无限次操作，每次操作的含义为： 输入1:你需要把(x,y)(第x行第y列)的格子权值增加a 输入2:你需要求出以左下角为(x1,y1),右上角为(x2,y2)的矩阵内所有格子的权值和,…
sql子查询示例_SQL更新查询示例说明
sql子查询示例In this article, were going to learn how to use the SQL update statement - what it is, what it can do, and what you need to be aware of before using it.在本文中，我们将学习如何使用SQL更新语句-它是什么，它可以做什么以及在使用…
keepalived+nginx安装
安装keepalivednginx做为公司服务器前端高可用反向代理安装nginx 1、yum install -y pcre pcre-devel gcc-c zlib zlib-devel openssl openssl-devel 2、cd /usr/local/soft 3、wget http://nginx.org/download/nginx-1.12.2.tar.gz 4、tar -zxvf nginx-1.12.2.tar.gz 5、cd ng…