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

zhenjen

找最大子区间的算法，改改应该用

zhangjinxuan

zhenjen 发表于 2023-6-6 11:31
找最大子区间的算法，改改应该用

那么我们怎么求出每个子区间的最大公因数呢

zhenjen

不知道，但可以上网查找

zhangjinxuan

zhenjen 发表于 2023-6-6 11:36
不知道，但可以上网查找

网上找不到我才问的，chatgpt 回答的也是 O(N^2) 算法。

zhenjen

时间复杂度要求是o（n）？

zhangjinxuan

zhenjen 发表于 2023-6-6 11:40
时间复杂度要求是o（n）？

是的，因为你看，1 <= n <= 1000000，但是 1 <= a_i <= 1000000，可以根据这一条下手

zhenjen

n是数据范围，那a_i是什么？

zhangjinxuan

zhenjen 发表于 2023-6-6 11:42
n是数据范围，那a_i是什么？

n 是数组长度，a_i 表示 a 的任一元素

zhenjen

n是长度，a是数字？

zhangjinxuan

zhenjen 发表于 2023-6-6 11:44
n是长度，a是数字？

n 是长度，a 是一个数组，a_i 表示 a 的第 i 个元素，在这里可能不太清晰，这个意思就是，a 的所有元素都大于等于 1，小于等于 1000000

zhenjen

时间复杂度没有要求。

zhangjinxuan

zhenjen 发表于 2023-6-6 11:46
时间复杂度没有要求。

时间复杂度自己想，想一想怎样的时间复杂度才能在 1s 以内通过此题。

zhenjen

zhangjinxuan 发表于 2023-6-6 11:47
时间复杂度自己想，想一想怎样的时间复杂度才能在 1s 以内通过此题。

我推荐看下找最大子区间的算法.算法时间复杂有on

zhangjinxuan

zhenjen 发表于 2023-6-6 11:56
我推荐看下找最大子区间的算法.算法时间复杂有on

但是这里还有最大公因数，只有求和都会做嗷。

zhangjinxuan

顶

zhangjinxuan

顶

zhangjinxuan

顶

yinda_peng

maybe，可以分治？我不会，你可以试试要求GPT写出O(n)复杂度的代码

zhangjinxuan

yinda_peng 发表于 2023-6-8 20:53
maybe，可以分治？我不会，你可以试试要求GPT写出O(n)复杂度的代码

分治

说详细点呢？说个“也许”有点半对不对的感觉。

我问了 GPT 的，大多都是 O(n^2)

tommyyu

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