python 中国剩余定理 chinese-remainder-theorem

1.题目2.编程思路及代码3.其他参考文献

1.题目

描述 给出两个数组 num[0..k - 1] 和 rem[0..k - 1]. 在数组num[0..k - 1]中, 所有的元素都是互质的( gcd 为 1 ). 我们需要找到满足下列条件的最小正数 x: x % num[0] = rem[0], x % num[1] = rem[1], ....................... x % num[k-1] = rem[k-1] 样例 样例 1: 输入：[3,4,5]，[2,3,1] 输出：11 解释： 11 是满足以下条件的最小值: - 除以 3, 得到余数 2。 - 除以 4, 得到余数 3。 - 除以 5, 得到余数 1。 样例 2: 输入：[3,4,5,11]，[2,3,1,7] 输出：491 解释： 491 是满足以下条件的最小值: - 除以 3, 得到余数 2。 - 除以 4, 得到余数 3。 - 除以 5, 得到余数 1。 - 除以 11, 得到余数 7。

2.编程思路及代码

solution 1：首先想到的是使用除数中最大的值的倍数+余数，不断增大，直到满足所有要求。可惜Time Limit Exceeded，通不过。

class Solution: """ @param num: the given array @param rem: another given array @return: The minimum positive number of conditions to meet the conditions """ def remainderTheorem(self, num, rem): # write your code here mx=max(num) ind=num.index(mx) mr=rem[ind] num.pop(ind) rem.pop(ind) n=len(num) k=0 while True: argmin=k*mx+mr j=0 for i in range(n): j+=1 if argmin%num[i]!=rem[i]: break if j==n: return argmin k+=1

solution 2：开始在网上搜索解决方法，终于找到了孙子定理/中国余数定理。 参考文件[1]和[2]给出了很好的介绍，这里只给出其精华部分。

引自参考文献1： 问题1：计算一个整数 [公式] ，使得它满足除以3余2、除以5余3、除以7余2。

如果能够找到三个整数 $x_1,x_2,x_3$ ，使得：

$x_1$ 除以3余2、除以5余0、除以7余0；

$x_2$ 除以3余0、除以5余3、除以7余0；

$x_3$ 除以3余0、除以5余0、除以7余2；

令 $x=x_1+x_2+x_3$，易知$x$ 满足除以3余2、除以5余3、除以7余2。

进一步将问题转化为：

$$\begin{gathered} x_1=2\ast y_1 \\ {x}_2=3\ast y_2 \\ {x}_3=2\ast y_3 \end{gathered}$$，使得：

$y_1$ 除以3余1、除以5余0、除以7余0；

$y_2$ 除以3余0、除以5余1、除以7余0；

$y_3$ 除以3余0、除以5余0、除以7余1;

则：$x=2\ast y_1+3\ast y_2+2\ast y_3$

如$y_1满足除以5余0、除以7余0$，则$y_1=5\ast 7\ast k$

又$y_1\mathrm{m}\mathrm{o}\mathrm{d}3=1，则取k=2.$

得到： $x=2\ast 70+3\ast 21+2\ast 15=233$

最后一步，x对所有除数的乘积取模运算，得到最小的满足解：

$x=x\mathrm{m}\mathrm{o}\mathrm{d}(3\ast 5\ast 7)=23$

本人的实现代码如下：

class Solution: """ @param num: the given array @param rem: another given array @return: The minimum positive number of conditions to meet the conditions """ def remainderTheorem(self, num, rem): # write your code here ls=[] k=1 for item in num: k*=item for i in range(len(num)): elem=k//num[i] j=1 while elem*j%num[i]!=1: #找到最小满足的k值 j+=1 ls.append(elem*j*rem[i]) res=sum(ls)%k return res

3.其他

如果存在余数相同的项，可通过将对应的除数相乘，这样少了一些项，但是好像也没节约时间。这里就不介绍了。

参考文献

[1] 知乎–中国剩余定理（CRT ） [2] 百度百科–孙子定理