今天朋友问了一个问题，
已知正整数 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的最小正剩余。