大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
孙子问题
最早，在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？用白话描述就是，现在有一个数不知道是多少，只知道这个数除以3余2，除以5余3，除以7余2， 问这个数是多少？
上面的问题可以转换为以下这样一个方程组:
{ x m o d 3 = 2 x m o d 5 = 3 x m o d 7 = 2 \begin{cases} x \quad mod \quad 3 =2\\ x \quad mod \quad 5 =3\\ x \quad mod \quad 7 =2\\ \end{cases} ⎩⎪⎨⎪⎧xmod3=2xmod5=3xmod7=2
其中这个 x x x就是我们要求的数。而中国剩余定理就是用来解决上述形式的方程组的 x x x解的。
解答讲解
在开始解答这个问题之前，我们先来了解一下几个数论基本知识。
基本等式
( 1 ) a m o d b = ( a + k ∗ b ) m o d b (1)a \quad mod \quad b=(a+k*b) \quad mod \quad b (1)amodb=(a+k∗b)modb
( 2 ) ( a ∗ k ) m o d b = k ∗ ( a m o d b ) (2)(a*k) \quad mod \quad b=k*(a \quad mod \quad b) (2)(a∗k)modb=k∗(amodb)
需要注意: a ≡ b ( m o d c ) \\a \equiv b(mod \quad c) a≡b(modc)的意思是 a m o d c = b m o d c a \quad mod \quad c = b \quad mod \quad c amodc=bmodc
在了解两个基本等式之后我们就可以对上述方程组做一些变换了:
{ x = k 1 ∗ 3 + 2 x = k 2 ∗ 5 + 3 x = k 3 ∗ 7 + 2 \begin{cases} x =k_1*3+2\\ x =k_2* 5 +3\\ x =k_3*7+ 2\\ \end{cases} ⎩⎪⎨⎪⎧x=k1∗3+2x=k2∗5+3x=k3∗7+2
直接看上面的方程组，好像直接求解出 k 1 、 k 2 、 k 3 k_1、k_2、k_3 k1、k2、k3不太现实，所以我们需要另寻出路。在这里我们先假设三个数，分别是 n 1 、 n 2 、 n 3 n_1、n_2、n_3 n1、n2、n3,满足一下条件:
{ n 1 m o d 3 = 2 n 2 m o d 5 = 3 n 3 m o d 7 = 2 \begin{cases} n_1 \quad mod \quad 3=2\\ n_2 \quad mod \quad 5=3\\ n_3 \quad mod \quad 7=2\\ \end{cases} ⎩⎪⎨⎪⎧n1mod3=2n2mod5=3n3mod7=2
假如 n 2 、 n 3 n_2、n_3 n2、n3均能整除3的话，那么按照等式 ( 1 ) (1) (1)就有:
{ n 2 = k 2 ′ ∗ 3 n 3 = k 3 ′ ∗ 3 \begin{cases} n_2 =k_2’*3\\ n_3 =k_3’*3\\ \end{cases}\\ {
n2=k2′∗3n3=k3′∗3
( n 1 + k 2 ′ ∗ 3 + k 3 ′ ∗ 3 ) m o d 3 = n 1 m o d 3 = 2 ( n 1 + n 2 + n 3 ) m o d 3 = 2 (n_1+k_2’*3+k_3’*3) \quad mod \quad 3=n_1 \quad mod \quad 3=2\\ (n_1+n_2+n_3) \quad mod \quad 3 =2\\ (n1+k2′∗3+k3′∗3)mod3=n1mod3=2(n1+n2+n3)mod3=2
那么我们继续假如 n 1 、 n 3 n_1、n_3 n1、n3能被5整除， n 1 、 n 2 n_1、n_2 n1、n2能被7整除，那么就有:
{ ( n 1 + n 2 + n 3 ) m o d 3 = 2 ( n 1 + n 2 + n 3 ) m o d 5 = 3 ( n 1 + n 2 + n 3 ) m o d 7 = 2 \begin{cases} (n_1+n_2+n_3) \quad mod \quad 3=2\\ (n_1+n_2+n_3) \quad mod \quad 5=3\\ (n_1+n_2+n_3) \quad mod \quad 7=2\\ \end{cases} ⎩⎪⎨⎪⎧(n1+n2+n3)mod3=2(n1+n2+n3)mod5=3(n1+n2+n3)mod7=2
对比题目中的方程组，可以看出只要满足以下条件就能使我们需要求解的 x = ( n 1 + n 2 + n 3 ) x=(n_1+n_2+n_3) x=(n1+n2+n3):
- n 1 n_1 n1除以3余2，且是5和7的公倍数。
- n 2 n_2 n2除以5余3，且是3和7的公倍数。
- n 3 n_3 n3除以7余2，且是3和5的公倍数。
我们只需要将 n 1 、 n 2 、 n 3 n_1、n_2、n_3 n1、n2、n3求出来后相加即可得我们想求的 x x x值。不过，这只是其中一个解，并不是最小解。要求最小解我们还需要除以 n 1 、 n 2 、 n 3 n_1、n_2、n_3 n1、n2、n3的最大公约数。
这里呢，我们以 n 1 n_1 n1求解为例， n 2 、 n 3 n_2、n_3 n2、n3求解过程类似。
求解 n 1 n_1 n1过程
首先我们先罗列一下基本约束条件:
{ n 1 m o d 3 = 2 n 1 = 5 ∗ k 2 ′ n 1 = 7 ∗ k 3 ′ \begin{cases} n_1 \quad mod \quad 3 =2\\ n_1 = 5 * k_2’\\ n_1 = 7 * k_3’\\ \end{cases} ⎩⎪⎨⎪⎧n1mod3=2n1=5∗k2′n1=7∗k3′
根据等式 ( 2 ) (2) (2)，可以得到:
n 1 m o d 3 = 2 ∗ ( n 1 2 m o d 3 ) = 2 n_1 \quad mod \quad 3 =2*(\dfrac{n_1}{2} \quad mod \quad 3)=2 n1mod3=2∗(2n1mod3)=2
n 1 2 m o d 3 = 1 \dfrac{n_1}{2} \quad mod \quad3 =1 2n1mod3=1
如果 n 1 2 \dfrac{n_1}{2} 2n1是5、7的整数倍，那么 n 1 n_1 n1自然也是5、7的整数倍。不过在这里呢，我们并没有从5和7的公倍数中直接找一个除以3余2的数，而是先找一个除以3余1的数，再乘以2。也就是先求出5和7的公倍数模3下的逆元，再用逆元去乘余数。具体过程如下:参考来源
推算过程如下:
首 先 我 们 令 K = n 1 2 , 首先我们令K=\dfrac{n_1}{2}, 首先我们令K=2n1,
因 为 K m o d 3 = 1 ( K 是 5 和 7 的 整 数 倍 ) , 所 以 g c d ( 5 ∗ 7 , 3 ) = 1 , 即 35 与 3 互 质 ， 由 拓 展 欧 几 里 得 算 有 : K ≡ 1 ( m o d 3 ) ⇒ K = a ∗ x = ( 5 ∗ 7 ) ∗ x ≡ 1 ( m o d 3 ) 35 ∗ x + 3 ∗ y = 1 ⇒ 整 数 解 为 : { x = 2 , y = − 23 , 可 求 得 a 的 逆 元 x = 2 , 则 K = 70 ⇒ n 1 = 2 ∗ K = 140 因为\\\quad K \quad mod \quad3 =1(K是5和7的整数倍),\\所以\\\quad gcd(5*7,3)=1,即35与3互质，由拓展欧几里得算有:\\\quad K\equiv1(mod \quad3)\Rarr K=a*x=(5*7)*x\equiv1(mod \quad 3)\\\quad 35*x+3*y=1\Rarr整数解为:\begin{cases}x=2,\\y=-23,\end{cases}\\可求得a的逆元x=2,则K=70\Rarr n_1=2*K=140 因为Kmod3=1(K是5和7的整数倍),所以gcd(5∗7,3)=1,即35与3互质，由拓展欧几里得算有:K≡1(mod3)⇒K=a∗x=(5∗7)∗x≡1(mod3)35∗x+3∗y=1⇒整数解为:{
x=2,y=−23,可求得a的逆元x=2,则K=70⇒n1=2∗K=140
类 似 , 可 求 出 n 2 = 63 ， n 3 = 30 ⇒ x = ( n 1 + n 2 + n 3 ) = 233 类似,可求出n_2=63，n_3=30\Rarr x=(n_1+n_2+n_3)=233 类似,可求出n2=63，n3=30⇒x=(n1+n2+n3)=233
不 过 此 时 并 不 是 最 小 数 ， 我 们 还 需 要 将 233 ÷ ( 3 、 5 、 7 ) 最 大 公 约 数 105 = 23 ， 这 才 是 符 合 条 件 的 最 小 数 不过此时并不是最小数，我们还需要将233\div(3、5、7)_{最大公约数105}=23，这才是符合条件的最小数 不过此时并不是最小数，我们还需要将233÷(3、5、7)最大公约数105=23，这才是符合条件的最小数
最大公倍数=各个数的乘积 ÷ \div ÷最大公约数，最大公约数可使用辗转相除法获取(欧几里得算法)
中国剩余定理公式
设正整数 m 1 , m 2 , . . . , m k , m_1,m_2,…,m_k, m1,m2,...,mk,两两互素，则同余方程组:
{ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) . . . . . . x ≡ a k ( m o d m k ) \begin{cases} x\equiv a_1(mod \quad m_1)\\ x\equiv a_2(mod \quad m_2)\\ ……\\ x\equiv a_k(mod \quad m_k)\\ \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧x≡a1(modm1)x≡a2(modm2)......x≡ak(modmk)
有整数解。并且在模 M = m 1 ∗ m 2 ∗ . . . ∗ m k M=m_1*m_2*…*m_k M=m1∗m2∗...∗mk下的解是唯一的，解为
x ≡ ( a 1 M 1 M 1 − 1 + a 2 M 2 M 2 − 1 + . . . + a k M k M k − 1 ) m o d M x\equiv(a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+…+a_kM_kM_k^{-1})mod \quad M x≡(a1M1M1−1+a2M2M2−1+...+akMkMk−1)modM
其中 M i = M m i M_i=\dfrac{M}{m_i} Mi=miM，而 M i M_i Mi模 m i m_i mi的逆元。
关于扩展欧几里得算法
参考文章:欧几里德算法与扩展欧几里德算法
用途
用来求解形如 a x + b y = c ( a , b , c ∈ Z ) ax + by = c(a, b, c \in Z) ax+by=c(a,b,c∈Z)的方程的一组整数解.。
使用条件
c m o d g c d ( a , b ) = 0 , g c d ( a , b ) 表 示 a / b 的 最 大 公 约 数 c \quad mod \quad gcd(a,b)=0,gcd(a,b)表示a/b的最大公约数 cmodgcd(a,b)=0,gcd(a,b)表示a/b的最大公约数
求解过程
求 解 方 程 : a x + b y = g c d ( a , b ) 求解方程:ax+by=gcd(a,b)\\ 求解方程:ax+by=gcd(a,b)
( 1 ) 当 b = 0 时 ， 原 方 程 可 化 为 a x = g c d ( a , 0 ) ⇒ 解 得 : { x = 1 y = 0 (1)当 b = 0 时，原方程可化为 ax = gcd(a, 0) \Rarr 解得:\begin{cases}x=1\\y=0 \end{cases} (1)当b=0时，原方程可化为ax=gcd(a,0)⇒解得:{
x=1y=0
( 2 ) 设 a ′ = b , b ′ = a m o d b , 有 如 下 方 程 : (2)设 a’ = b, b’ = a \quad mod \quad b,有如下方程: (2)设a′=b,b′=amodb,有如下方程:
{ a ′ x ′ + b ′ y ′ = g c d ( a ′ , b ′ ) = g c d ( b , a m o d b ) a x + b y = gcd ( a , b ) \begin{cases} a’x’+b’y’=gcd(a’,b’)=gcd(b,a \quad mod \quad b)\\ ax + by = \gcd(a, b) \end{cases} {
a′x′+b′y′=gcd(a′,b′)=gcd(b,amodb)ax+by=gcd(a,b)
另 有 恒 等 式 : g c d ( a , b ) = g c d ( b , a m o d b ) ， 则 : 另有恒等式:gcd(a,b)=gcd(b,amodb)，则: 另有恒等式:gcd(a,b)=gcd(b,amodb)，则:
a x + b y = a ′ x ′ + b ′ y ′ = b x ′ + ( a m o d b ) y ′ = b x ′ + ( a − ⌊ a b ⌋ b ) y ′ ax+by=a’x’+b’y’=bx’+(a\quad mod\quad b)y’=bx’+(a−⌊\dfrac{a}{b}⌋b)y’ ax+by=a′x′+b′y′=bx′+(amodb)y′=bx′+(a−⌊ba⌋b)y′
整 理 得 : 整理得: 整理得:
a x + b y = = b x ′ + ( a − ⌊ a b ⌋ b ) y ′ ⇓ { x = y ′ y = x ′ − ⌊ a b ⌋ y ′ ax+by==bx’+(a−⌊\dfrac{a}{b}⌋b)y’\\ \Darr\\ \begin{cases} x=y’\\ y=x’−⌊\dfrac{a}{b}⌋y’ \end{cases} ax+by==bx′+(a−⌊ba⌋b)y′⇓{
x=y′y=x′−⌊ba⌋y′
通过上述这个解可知道，如果反复迭代递归，最终一定会到达临界条件 b = 0 b=0 b=0,即情况 ( 1 ) (1) (1),从而计算出最终值。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/215476.html原文链接：https://javaforall.net
