中国剩余定理【数论】

2019-04-13 21:54发布

站内文章 / 模拟电子
13560 0 1242
中国剩余定理的具体描述是这样的：
给出你n个ai和mi，最后让求出x的最小值是多少。 中国剩余定理说明：假设整数m1, m2, ... , mn两两互质，则对任意的整数：a1, a2, ... , an，方程组(S)有解，并且通解可以用如下方式构造得到：
  1. 设M = m_1 imes m_2 imes cdots imes m_n = prod_{i=1}^n m_i是整数m1, m2, ... , mn的乘积，并设M_i = M/m_i, ; ; forall i in {1, 2, cdots , n}是除了mi以外的n - 1个整数的乘积。
  2. 设t_i = M_i^{-1}为M_i模m_i的数论倒数：t_i M_i equiv 1 pmod {m_i}, ; ; forall i in {1, 2, cdots , n}.
  3. 方程组(S)的通解形式为：x = a_1 t_1 M_1 + a_2 t_2 M_2 + cdots + a_n t_n M_n + k M= k M + sum_{i=1}^n a_i t_i M_i, quad k in mathbb{Z}. 在模M的意义下，方程组(S)只有一个解：x = sum_{i=1}^n a_i t_i M_i.

            分割线                                                                                                                   
下面我们来看一个具体的例子：
使用中国剩余定理来求解上面的“物不知数”问题，便可以理解《孙子歌诀》中的数字含义。这里的线性同余方程组是：
(S) : quad left{ egin{matrix} x equiv 2 pmod {3} \ x equiv 3 pmod {5} \ x equiv 2 pmod {7} end{matrix} ight.
三个模数m1=3, m2=5, m3=7的乘积是M=105，对应的M1=35, M2=21, M3=15. 而可以计算出相应的数论倒数：t1=2, t2=1, t3=1. 所以《孙子歌诀》中的70，21和15其实是这个“物不知数”问题的基础解：
70 = 2 imes 35 equiv left{ egin{matrix} 1 pmod {3} \ 0 pmod {5} \ 0 pmod {7} end{matrix} , ight. 21 = 1 imes 21 equiv left{ egin{matrix} 0 pmod {3} \ 1 pmod {5} \ 0 pmod {7} end{matrix} , ight. 15 = 1 imes 15 equiv left{ egin{matrix} 0 pmod {3} \ 0 pmod {5} \ 1 pmod {7} end{matrix} , ight.
而将原方程组中的余数相应地乘到这三个基础解上，再加起来，其和就是原方程组的解：
2 imes 70 + 3 imes 21 + 2 imes 15 equiv left{ egin{matrix} 2 imes 1 + 3 imes 0 + 2 imes 0 equiv 2 pmod {3} \ 2 imes 0 + 3 imes 1 + 2 imes 0 equiv 3 pmod {5} \ 2 imes 0 + 3 imes 0 + 2 imes 1 equiv 2 pmod {7} end{matrix} , ight.
这个和是233，实际上原方程组的通解公式为：
x = 233 + k imes 105, ; kin mathbb{Z}.
《孙子算经》中实际上给出了最小正整数解，也就是k=-2时的解：x=23.
附：数论倒数 wiki
具体代码参考如下：（应该很明了） ///n个mi互质 const LL maxn = 20; LL a[maxn], m[maxn], n; LL CRT(LL a[], LL m[], LL n) { LL M = 1; for (int i = 0; i < n; i++) M *= m[i]; LL ret = 0; for (int i = 0; i < n; i++) { LL x, y; LL tm = M / m[i]; ex_gcd(tm, m[i], x, y); ret = (ret + tm * x * a[i]) % M; } return (ret + M) % M; }
       分割线                                                                                                                       
下面也就是关于这个的扩展，前面我们已经说了，中国剩余数定理是适用于n个mi两两互质的情况的，如果不互质呢，下面就是一个转换： 模不两两互质的同余式组可化为模两两互质的同余式组，再用孙子定理直接求解。 84=22×3×7,160=25×5,63=32×7，由推广的孙子定理可得 egin{cases}x equiv 23 pmod{84} \x equiv 7 pmod{160} \x equiv 2 pmod{63} end{cases} 与 egin{cases}x equiv 7 pmod{2^5} \x equiv 2 pmod{3^2} \x equiv 7 pmod{5} \x equiv 23 pmod{7}end{cases} 同解。 附图：详细讲解，转自传送门


///n个mi不互质 const LL maxn = 1000; LL a[maxn], m[maxn], n; LL CRT(LL a[], LL m[], LL n) { if (n == 1) { if (m[0] > a[0]) return a[0]; else return -1; } LL x, y, d; for (int i = 1; i < n; i++) { if (m[i] <= a[i]) return -1; d = ex_gcd(m[0], m[i], x, y); if ((a[i] - a[0]) % d != 0) return -1; //不能整除则无解 LL t = m[i] / d; x = ((a[i] - a[0]) / d * x % t + t) % t; //第0个与第i个模线性方程的特解 a[0] = x * m[0] + a[0]; m[0] = m[0] * m[i] / d; a[0] = (a[0] % m[0] + m[0]) % m[0]; } return a[0]; }
                                                                                                          以上大部分内容来自wiki 下面做几道练手的题目： poj2891，n个mi不互质的裸题 代码 poj1006，三个互质的裸题 代码





热门文章