多元一次不定方程的强力算法:同余筛数法
今天朋友问了一个问题， 已知正整数 s 和正整数集合 j1 j2 j3… jn , 未知正整数 k1 k2 k3…kn，使得s = j1 * k1 + j2 * k2 + j3 * k3 + jn * kn，要求 k1 k2 k3…kn的值。 这个凑单时经常用到，如定好每件商品的单价以及总金额，要求出每样商品的数量。 一个简单的例子 看一个简单的例子，有若干的 1块，2块，5块的纸币，凑100块钱。 即 1x + 2y + 5*z = 100 这个是多元一次不定方程。这在数论里面有研究，通过通解来求解特定范围的解理论上虽然可行，但遗憾的是其求解效率几乎与穷举法相当的。 同余筛数法 下面介绍一种比上述方案更快速的强力快速算法。这是一种基于同余理论的快速算法，同余筛数法。 原理 我们知道二元不定方程 a * x + b * y = c 其实是与同余方程 a * x = c (mod b) 等价的。 同理对于三元不定方程 a * x + b * y + c * z = d ，实际上也可以理解成 a * X = p (mod c)，b * Y = q (mod c)，设d = d' (mod c)，则有 p + q = d' (mod d)。 为什么会有这样的结论？原因很简单：d - a * x + b * y = c * t0 + d' - a * c * t - p - b * c * t' - q = c * z = 0 (mod c)。...