文档章节

中国剩余定理

o
 osc_z1hvg4cu
发布于 2018/04/24 17:10
字数 2829
阅读 0
收藏 0
n2n

转载自:https://www.cnblogs.com/MashiroSky/p/5918158.html

先看一道poj上的题目:【poj1006】 Biorhythms

题意:

  人自出生起就有体力,情感和智力三个生理周期,分别为23,28和33天。一个周期内有一天为峰值,在这一天,人在对应的方面(体力,情感或智力)表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日期,分别对应于体力,情感,智力出现峰值的日期。然后再给出一个起始日期,要求从这一天开始,算出最少再过多少天后三个峰值同时出现。

分析:

  首先我们要知道,任意两个峰值之间一定相距整数倍的周期。假设一年的第N天达到峰值,则下次达到峰值的时间为N+TkN+Tk(TT是周期,kk是任意正整数)。所以,三个峰值同时出现的那一天(S)(S)应满足

S=N1+T1k1=N2+T2k2=N3+T3k3S=N1+T1∗k1=N2+T2∗k2=N3+T3∗k3

 

  N1,N2,N3N1,N2,N3分别为为体力,情感,智力出现峰值的日期, T1T2,T3T1,T2,T3分别为体力,情感,智力周期。 我们需要求出k1,k2,k3k1,k2,k3三个非负整数使上面的等式成立。

  想直接求出k1,k2,k3k1,k2,k3貌似很难,但是我们的目的是求出SS, 可以考虑从结果逆推。根据上面的等式,SS满足三个要求:除以T1T1余数为N1N1,除以T2T2余数为N2N2,除以T3T3余数为N3N3。这样我们就把问题转化为求一个最小数,该数除以T1T1余N1N1,除以T2T2余N2N2,除以T3T3余N3N3。这就是著名的中国剩余定理,我们的老祖宗在几千年前已经对这个问题想出了一个精妙的解法。依据此解法的算法,时间复杂度可达到O(1)O(1)。 


 中国剩余定理

  在《孙子算经》中有这样一个问题:“今有物不知其数,三三数之剩二(除以3余2),五五数之剩三(除以5余3),七七数之剩二(除以7余2),问物几何?”这个问题称为“孙子问题”,该问题的一般解法国际上称为“中国剩余定理”。具体解法分三步:

    1. 找出三个数:从3和5的公倍数中找出被7除余1的最小数15,从3和7的公倍数中找出被5除余1 的最小数21,最后从5和7的公倍数中找出除3余1的最小数70。
    2. 用15乘以2(2为最终结果除以7的余数),用21乘以3(3为最终结果除以5的余数),同理,用70乘以2(2为最终结果除以3的余数),然后把三个乘积相加152+213+70215∗2+21∗3+70∗2得到和233。
    3. 用233除以3,5,7三个数的最小公倍数105,得到余数23,即233%105=23233%105=23。这个余数23就是符合条件的最小数。

  就这么简单。我们在感叹神奇的同时不禁想知道古人是如何想到这个方法的,有什么基本的数学依据吗?

  我们将“孙子问题”拆分成几个简单的小问题,从零开始,试图揣测古人是如何推导出这个解法的。

  首先,我们假设n1n1是满足除以3余2的一个数,比如2,5,8等等,也就是满足3k+2k>=03∗k+2(k>=0)的一个任意数。同样,我们假设n2n2是满足除以5余3的一个数,n3n3是满足除以7余2的一个数。

  有了前面的假设,我们先从n1n1这个角度出发,已知n1n1满足除以3余2,能不能使得n1+n2n1+n2的和仍然满足除以3余2?进而使得n1+n2+n3n1+n2+n3的和仍然满足除以3余2?

  这就牵涉到一个最基本数学定理,如果有a%b=ca%b=c,则有(a+kb)%b=c(k)(a+k∗b)%b=c(k为非零整数),换句话说,如果一个除法运算的余数为cc,那么被除数与kk倍的除数相加(或相减)的和(差)再与除数相除,余数不变。这个是很好证明的。

  以此定理为依据,如果n2n2是3的倍数,n1+n2n1+n2就依然满足除以3余2。同理,如果n3n3也是3的倍数,那么n1+n2+n3n1+n2+n3的和就满足除以3余2。这是从n1n1的角度考虑的,再从n2n2,n3n3的角度出发,我们可推导出以下三点:

    1. 为使n1+n2+n3n1+n2+n3的和满足除以3余2,n2n2和n3n3必须是3的倍数。
    2. 为使n1+n2+n3n1+n2+n3的和满足除以5余3,n1n1和n3n3必须是5的倍数。
    3. 为使n1+n2+n3n1+n2+n3的和满足除以7余2,n1n1和n2n2必须是7的倍数。

  因此,为使n1+n2+n3n1+n2+n3的和作为“孙子问题”的一个最终解,需满足:

    1. n1n1除以3余2,且是5和7的公倍数。
    2. n2n2除以5余3,且是3和7的公倍数。
    3. n3n3除以7余2,且是3和5的公倍数。

  所以,孙子问题解法的本质是从5和7的公倍数中找一个除以3余2的数n1n1,从3和7的公倍数中找一个除以5余3的数n2n2,从3和5的公倍数中找一个除以7余2的数n3n3,再将三个数相加得到解。在求n1n1,n2n2,n3n3时又用了一个小技巧,以n1n1为例,并非从5和7的公倍数中直接找一个除以3余2的数,而是先找一个除以3余1的数,再乘以2。也就是先求出5和7的公倍数模3下的逆元,再用逆元去乘余数

  这里又有一个数学公式,如果a%b=ca%b=c,那么(ak)%b=a%b+a%b++a%b=c+c++c=kc(k>0)(a∗k)%b=a%b+a%b+…+a%b=c+c+…+c=k∗c(k>0),也就是说,如果一个除法的余数为cc,那么被除数的kk倍与除数相除的余数为kck∗c。展开式中已证明。

  最后,我们还要清楚一点,n1+n2+n3n1+n2+n3只是问题的一个解,并不是最小的解。如何得到最小解?我们只需要从中最大限度的减掉掉3,5,7的公倍数105即可。道理就是前面讲过的定理“如果a%b=ca%b=c,则有(akb)%b=c(a−k∗b)%b=c”。所以n1+n2+n3%105(n1+n2+n3)%105就是最终的最小解。

  这样一来就得到了中国剩余定理的公式:

设正整数两两互素,则同余方程组

                             

有整数解。并且在模下的解是唯一的,解为

                               

其中,而的逆元。

 


 

题目

x%ai = ri

X%5=3

X%7=4

X%9=2

X%10=1

 求x

 

 

题意:有一个数x,,给出n对ai和ri,问x的最小非负整数是什么,如果不存在输出-1

       这道题需要用到扩展欧几里德算法合并模线性方程组。由于这个题中所有的ai之间不一定能够保证两两互质,因而不满足中国剩余定理的条件,只能用扩展欧几里德算法对模线性方程组进行+合并。之前看网上讲了一堆关于合并模线性方程组的文章,但是还是有些不太懂。现在算是明白其中的道理。

Ax+by=c

X%a1=r1

X=x0+ k*lcm(a1,a2)

X%lcm(a1,a2)=x0

(x+k*lcm(a1,a2))%a1=r1

       假设x%a1=r1,x%a2=r2。那么我们将式子写开就变成了x=k1*a1+r1,x=k2*a2+r2。所以联立两个式子就可以得到k1*a1+r1=k2*a2+r2。那么移项可得a1*k1-a2*k2=(r2-r1)。得到这个式子后我们就可以利用扩展欧几里德算法求出k1,k2的值。这里要保证k1为正数。当k1为负数时,k1不断的加上a2/gcd(a1,a2),k2同时就要减去a1/gcd(a1,a2)。求出正数的k1以后,就可以计算出x的值。这里先暂时记作x0。我们知道这属于不定方程,所以x满足这两个模线性方程,x0+k*a1也满足两个模线性方程组,x0+k*a2也满足两个模线性方程。所以满足这两个模线性方程的x的通解为x=x0+ lcm(a1,a2)。lcm(a1,a2)是a1和a2的最小公倍数。我们将这个式子再次转换成模线性方程即得x%lcm(a1,a2)=x0。这样就可以逐步迭代求出最终满足条件的x值。

 

       当然这是不满足中国剩余定理的情况下对模线性方程组的合并。如果满足中国剩余定理即可根据中国剩余定理来合并。不过两种不同情形下对模线性方程组的合并,实质是一样的。

 

       还有需要说明的是扩展欧几里德算法中,出现ax-by=c(a,b,c均大于0)的情形。这不满足扩展欧几里德中的条件。因为这里我们需要求a和-b的gcd。这是不行的。因为扩展欧几里德算法说a和b必须满足a,b是不同时为0的非负数。所以我们适当变形。将上面的式子变为ax+b*(-y)=c。这样就可以正常计算了。而c的正负实际上只会影响到x,y的值。所以这样给y多加一个负号,到时候计算出结果时再将y的负号加上即可。

 

      这道题属于合并模线性方程组的一个类型。下面附上中国剩余定理对于合并模线性方程组的描述。

 

      下面摘自百度百科,感觉还是很重要的。

 

用现代数学的语言来说明的话,中国剩余定理给出了以下的一元线性同余方程组:

 

有解的判定条件,并用构造法给出了在有解情况下解的具体形式。

中国剩余定理说明:假设整数m1,m2, ... ,mn两两互质,则对任意的整数:a1,a2, ... ,an,方程组有解,并且通解可以用如下方式构造得到:

设是整数m1,m2, ... ,mn的乘积,并设是除了mi以外的n- 1个整数的乘积。

设为模的数论倒数:

方程组的通解形式为:在模的意义下,方程组只有一个解:

        中国剩余定理还是很重要的,比如对一个数取模,而这个数可以分解成几个互质的数,那么我们就可以分别对这几个互质的数进行取模,然后再用中国剩余定理合并。比较难的题中中国剩余定理也会与矩阵快速幂等知识点相结合。比如HDU 4767等。

        参考代码:

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

OSChina 周五乱弹 —— 你大妈还是你大妈

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @watergood:是时候分享一波我的这张纯音乐歌单了,过去的五年多时间里,我陆陆续续地把听到的好听的纯音乐添加了进去,目前一共65首,相信总...

小小编辑
今天
25
0
在Objective-C中生成随机数 - Generating random numbers in Objective-C

问题: I'm a Java head mainly, and I want a way to generate a pseudo-random number between 0 and 74. In Java I would use the method: 我主要是Java头,我想要一种生成0到74之间的伪随......

技术盛宴
今天
13
0
ftp-ftps-sftp的关系

Ftp FTP 是File Transfer Protocol(文件传输协议)的英文简称,而中文简称为“文传协议”。用于Internet上的控制文件的双向传输。同时,它也是一个应用程序(Application)。基于不同的操作...

独钓渔
今天
12
0
使Vim将所有空格显示为字符 - Make Vim show ALL white spaces as a character

问题: I can't find a way to make Vim show all white spaces as a character. 我找不到让Vim将所有空白显示为字符的方法。 All I found was about tabs, trailing spaces etc. 我发现的只......

富含淀粉
今天
23
0
RN 接入高德地图遇到的一些问题

react-native-amap-geolocation、react-native-amap3d 1、iOS Geolocation.getCurrentPosition 获取坐标后,没有返回 address 信息? 逆地理编码 Android 默认返回逆地理编码,而 iOS 需要手...

Jack088
今天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部