区间 gcd 与总和的和最大值问题，这个问题有点不会，望高人赐教，谢谢【重金悬赏】

tommyyu

例子里面不应该是 gcd(9, 8, 16, 24) + 9 + 8 + 16 + 24 = 58 么？

tommyyu

我有了一个思路，但是懒得写代码了
首先，如果选择所有数，那么最终的结果就应该是 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 时，可以直接进行剪枝，并跳出循环。

zhangjinxuan

tommyyu 发表于 2023-6-10 09:51
我有了一个思路，但是懒得写代码了
首先，如果选择所有数，那么最终的结果就应该是 a1 + ... + an + gcd(a ...

好的，我尝试一下，谢谢您的耐心答复！

zhangjinxuan

tommyyu 发表于 2023-6-10 09:51
我有了一个思路，但是懒得写代码了
首先，如果选择所有数，那么最终的结果就应该是 a1 + ... + an + gcd(a ...

那么可以解释一下 4  9 8 16 24 是怎么得出 2 4  56 的呢？

tommyyu

zhangjinxuan 发表于 2023-6-10 10:30
那么可以解释一下 4  9 8 16 24 是怎么得出 2 4  56 的呢？

不太清楚，可能是代码的问题，或者是我的思路有问题

zhangjinxuan

tommyyu 发表于 2023-6-10 10:49
不太清楚，可能是代码的问题，或者是我的思路有问题

陈尚涵

zhangjinxuan 发表于 2023-6-6 07:51
37 行，j 应该是第几个质数，所以不应该是 a[ i] % sieve[j] == 0 吗？

还有，你这样的时间复杂度是 ...

我连n^2算法都问不出来

zhangjinxuan

陈尚涵 发表于 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:}

陈尚涵

zhangjinxuan 发表于 2023-6-11 20:22
{:10_277 ...

我的gpt太笨了

zhangjinxuan

陈尚涵 发表于 2023-6-11 20:40
我的gpt太笨了

给它数据范围，并且强调 O(N^2) 或者 O(N)

陈尚涵

zhangjinxuan 发表于 2023-6-11 20:46
给它数据范围，并且强调 O(N^2) 或者 O(N)

我的意思是他都无法写正确

zhangjinxuan

陈尚涵 发表于 2023-6-11 20:48
我的意思是他都无法写正确