算法:找到最小的倍数

Question

让有一些正整数 Z 并让有一个 N 的列表，非负整数标记为 z0 ... zn-1 什么是可以找到 Z 的最小倍数的算法所有 zi * ci 的总和，其中 ci 是任何非负整数常量？

这个算法需要及时运行 O(Z * ( N + log(Z) )).

我尝试使用 djikstras 算法解决此问题，并尽可能确定必须有 Z * N 条边和 Z 条顶点才能满足时间复杂度要求。我还发现每个 ni 最多可以有 Z 个不同的系数，因为 (min zi)/zi * Z 受 Z 约束。

也许有某种方法可以通过探索循环图设置来做到这一点？

Answer 1

您应该查找 Frobenius problem (或麦乐鸡问题)。

给定两个相对质数的整数(a,b)，所有数>= (a-1)(b-1) + 1都可以写成xa + yb 用于非负整数 x,y。

使用它，您的搜索空间会大大减少。