UC知道关于剩余定理不互质的问题
来源：百度知道 编辑：UC知道 时间：2024/05/17 02:22:04
有某数 N
N 除 a 余 1
N 除 b 余 2
N 除 c 余 3
N 除 d 余 4
但a,b,c,d不满足两两互质
那该怎么用剩余定理的思想求 N 呢？
如果是分别找两个数的最大公约数，再用这两个数除以这个最大公约数的话就算了，数据量一大就麻烦了，有没有更简单的方法？
麻烦哪位高手讲解一下。
a,b,c,d不两两互质的情况下怎么办？
N 除 a 余 1
N 除 b 余 2
N 除 c 余 3
N 除 d 余 4
但a,b,c,d不满足两两互质
那该怎么用剩余定理的思想求 N 呢？
如果是分别找两个数的最大公约数，再用这两个数除以这个最大公约数的话就算了，数据量一大就麻烦了，有没有更简单的方法？
麻烦哪位高手讲解一下。
a,b,c,d不两两互质的情况下怎么办？
典型的韩信点兵
用数学方法最简单 写程序也可以
http://baike.baidu.com/view/350224.htm
因式分解
x=7 (mod 16)
x=15 (mod 24)
等价于
x=7 (mod 16)
x=15=7 (mod 8)
x=15=0 (mod 3)
x=231=(7*3*11+0*16*1) (mod 48)