给定一个数字K和一组已排序的数字。查找集合中是否有任何数字可以整除K。

Question

给定一个数字k和一组排序数字。查找是否有任何数字在集合中可以被这个数字整除。

例如，如果k = 8，集合是{3, 4, 5}，那么4将会整除8，4就是答案。

最坏情况的解决方案是O(n)。

我们能做得更好吗？

- sunmoon

---

你能描述一下你最糟糕的解决方案吗？到目前为止，你自己有什么想法？此外，这个集合是否总是包含连续的数字？为什么4是答案？2也可以被8整除。 - Björn Pollex

为什么2不是答案？ - Naveen

@Naveen：2也是一个答案，但问题要求找出是否至少有一个数字。 - Shamim Hafiz - MSFT

你可以在满足 O(sqrt(k)*log(n)) 小于 O(n) 的情况下进行操作。生成 k 的所有因子，然后在集合中查找每个因子。 - Steve Jessop

@sunmoon，你已经编辑了你的集合，但是它们不再排序。我认为排序对于找到更优解是一个重要因素。 - Jim Balter

Answer 1

如果您想要更快地找出一个大数据集中的因数，可以将该数字进行分解（例如8分解为4、2、1），然后在给定的集合中查找这些因数。您可以使用集合交集或双分搜索您的因数列表。我认为这样做可以更快地得出答案。

- Lmwangi

---

什么是分解一个数的最佳方法？ - sunmoon

...但是你必须将集合中的数字进行因式分解，以便进行正确的交集运算 - 除非我漏掉了什么。 - ltjax

关于这个问题，我不这么认为，因为他说“查找集合中是否有任何一个数可以整除这个数”。所以我们正在查找我们的因子是否在集合中。没有更多了。想到集合交集，我认为它们会表现得很差，因为按定义，它们是无序的，并且交集是O(n)。哎呀！所以我会使用因子的二分搜索- http://en.wikipedia.org/wiki/Binary_search_algorithm - Lmwangi

+1，只要查询的数字不太大且集合非常大，我认为这是一个很好的解决方案。对于非常大的值和小的集合，O(n)搜索会更快。 - MAK

@Space_cowboy：对于大数和小集合，分解这个数字会很昂贵。也许采用混合方法会有所帮助，其中我们（1）从排序集合中选择最大的整数（X），（2）如果我们得到的因子比X大，则停止分解提供的数字，（3）将我们的因子列表与我们的排序列表进行比较。你觉得呢？ - Lmwangi

Answer 2

计算k和集合成员的乘积的最大公约数。例如，gcd(3*4*5,8) = 4。

- user448810

Answer 3

如果k是质数，则它在该集合中没有因子，您完成了。否则，k = p*q，其中p是k的最小因子。对q进行二进制搜索。如果找到，您完成了。否则，重构k=p'*q'，其中p'是p之后k的下一个最大因子--如果没有，则您完成了。否则，继续搜寻q'的二进制搜索--请注意，q'

编辑： 嗯...我想这不是O(logn)。例如，如果列表包含每个因子f的f-1，那么您必须按顺序为每个f搜索，每次都会击中f-1...那将是O(n)。

- Jim Balter