今天朋友问了一个问题,

已知正整数 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)

更一般化地我们有以下结论:

定理 : 设n元不定方程 ∑aixi = C 有解,则必有 C = C' (mod q) ,C' = ∑ri,其中ri是当xi取某一定值x’i时aixi关于q的最小正剩余。