我有一个问题要解决。任务是编写一个程序，该程序将针对给定的 N 个数字数组 ( N <= 10^5 )，打印一个新数组，该数组是通过将任意两个相邻元素连接成它们的总和而制成的，(总和正在替换这两个相邻元素并且数组的大小小 1)，直到数组的大小为 K。我需要打印一个解决方案，其中新元素的 GCD 最大化。 (并在打印数组后打印 GCD)。
注意:给定数组中所有元素的总和不大于 10^6。
我意识到我可以以某种方式使用前缀和，因为所有元素的总和不高于 10^6，但这对我帮助不大。
这个问题的最佳解决方案是什么？
最佳答案
您的 GCD 将是数组中所有元素之和的除数。你的和不大于 10^6，所以除数不大于 240，所以你可以检查所有这些 GCD，它会足够快。您可以检查是否可以在线性时间内询问 gcd:只需遍历数组，而当前总和不是所需 gcd 的除数。当只是将当前总和设置为0时，如果至少找到k个区 block ，就有可能得到当前gcd(可以加入任意2个区 block ，gcd都一样)。
关于algorithm - 将数组的两个相邻元素连接(求和)为一个元素，直到其大小为 K 并且新元素的 GCD 最大可能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57353228/