Posts Tagged ‘数论’

April 14, 2010
[算法]物不知数 – 中国剩余定理

　　设”此物”为x，则x满足同余方程组：
\left\{\begin{array}{c}x\equiv 2 (\mod 3)\\x\equiv 3 (\mod 5) \\x\equiv 2 (\mod 7)\end{array}\right.
　　若存在x满足上述方程组，则x + k*3*5*7也满足该方程其中k任意整数，方程的最小正整数解满足x\mod{3*5*7}，即对3,5,7的最小公倍数求余。
　　在介绍求x的具体方法之前，先介绍两个简单的定理(证明从略)：

  1. 被除数增加(或减少)除数的倍数，除数不变，则余数电不变；
  2. 被除数扩大(或缩小)指定的倍数，除数不变，则余数扩大(或缩小)同样的倍数(余数总小于除数)。
Tags: ,. 181 views
Filed under: 之算法神奇,数理空间,边走编程 — dutor @ 7:59 pm Comments (0)
Page 1 of 11