algorithm - 在数组中找到最小整数，它是所有先前整数的约数

Question

我一直在解决前几年的练习题，我遇到了一个我/怀疑/如果没有我不知道的数论关系就无法解决的问题。

问题是:

Given an array of N integers, find the smallest integer which is a divisor of all the previous integers.

现在的问题是，如果我无法缓存模运算的任何结果，那么复杂度将变为 O(n^2)，由于存在时间限制，因此运行速度不够快，无法通过问题的自动测试以及 300 万个元素的潜在大小。

是否有任何 f 和 g 使 f(d, g[a1, a2, a3, a4, ..., an])) 为真当且仅当 d | a1, d | a2, d | a3, ..., d |一个 ？如果没有，你们对解决问题的方法还有其他建议吗？

感谢任何帮助!

Answer 1

一个整除所有前面的元素当且仅当它整除这些元素的最大公约数。

因此您需要跟踪gcd(a1, a2, ..., an) 以及an | 的最小an gcd(...)。