我有了一个思路，但是懒得写代码了
首先，如果选择所有数，那么最终的结果就应该是 a1 + ... + an + gcd(a1,..., an)，但如果选了 al ~ ar， 结果就变成了al + ... + ar + gcd(al, ..., ar)
如果要找到结果最大，无非有两种选择：一是选择全部的数，二是选择一部分使 gcd 变大。若 al + ... + ar + gcd(al, ..., ar) > a1 + ... + an + gcd(a1, ..., an)，则
两边同时减去 (al + ... ar)，gcd(al, ..., ar) > a1 + ... + al-1 + ar+1 +... +an + gcd(a1, ..., an)
又因为 min(al, ..., ar) > gcd (al, ..., ar) > a1 + ... + al-1 + ar+1 +... +an + gcd(a1, ..., an) > a1 + ... + al-1 + ar+1 +... +an > max(a1 , ... , al-1 , ar+1 ,... ,an)
所以 我们选择的数中的最小值 应当大于 未选择的数中的最大值，即我们要选择前(r-l+1)大的数。
由此一切都变得明了了，我们只需要先把全部选择的结果算出来，然后对所有数进行一个排序，依次选择前1大、前2大……前n大（一次增加一个）的数，看他们是否能够连接成一个区间（也就是max(原索引) - min(原索引) = 选择数的数量-1），对能够连成区间的进行计算。
此外，当我们选择的前 x 大的数的 gcd 已经等于 原数列所有数的 gcd 时，可以直接进行剪枝，并跳出循环。
tommyyu 发表于 2023-6-10 09:51
我有了一个思路，但是懒得写代码了
首先，如果选择所有数，那么最终的结果就应该是 a1 + ... + an + gcd(a ...
好的，我尝试一下，谢谢您的耐心答复！
tommyyu 发表于 2023-6-10 09:51
我有了一个思路，但是懒得写代码了
首先，如果选择所有数，那么最终的结果就应该是 a1 + ... + an + gcd(a ...
那么可以解释一下 49 8 16 24 是怎么得出 2 456 的呢？
zhangjinxuan 发表于 2023-6-10 10:30
那么可以解释一下 49 8 16 24 是怎么得出 2 456 的呢？
{:10_277:}不太清楚，可能是代码的问题，或者是我的思路有问题
tommyyu 发表于 2023-6-10 10:49
不太清楚，可能是代码的问题，或者是我的思路有问题
{:10_291:}
zhangjinxuan 发表于 2023-6-6 07:51
37 行，j 应该是第几个质数，所以不应该是 a[ i] % sieve == 0 吗？
还有，你这样的时间复杂度是 ...
我连n^2算法都问不出来
陈尚涵 发表于 2023-6-11 20:09
我连n^2算法都问不出来
{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}{:10_277:}
zhangjinxuan 发表于 2023-6-11 20:22
{:10_277 ...
我的gpt太笨了
陈尚涵 发表于 2023-6-11 20:40
我的gpt太笨了
给它数据范围，并且强调 O(N^2) 或者 O(N)
zhangjinxuan 发表于 2023-6-11 20:46
给它数据范围，并且强调 O(N^2) 或者 O(N)
我的意思是他都无法写正确
陈尚涵 发表于 2023-6-11 20:48
我的意思是他都无法写正确
{:10_277:}