找到第一个元素可被第二个元素整除的对数

Question

假设有一些数字

8, 7, 6, 5, 4, 3, 2

你必须找到所有对(a, b)这里a之前在列表中出现b,和a%b = 0.

这里,这样的对是:

(8, 4), (8, 2), (6, 3), (6, 2), (4, 2)

有没有比O(n ²)更好的算法？

Answer 1

使用动态规划可以以复杂度 O(nlogn) 解决此问题。类似于硬币面额问题。

硬币面额问题解决方案请参考以下链接 硬币面额问题