zhenjen 发表于 2023-6-6 11:27
个人思路：1.找包含公因数的区间。h=gcd（）+包含公因数区间k，记录左右端点。n=h。2.加if（h＞n）更新记录 ...
给定一个正整数序列 a，请找到两个数 l, r，使 gcd(al, al+1, ..., ar) + al, al+1, ..., ar 最大，输出 l, r，并且输出这个最大值。
gcd 表示最大公因数。
找最大子区间的算法，改改应该用
zhenjen 发表于 2023-6-6 11:31
找最大子区间的算法，改改应该用
{:10_277:}
那么我们怎么求出每个子区间的最大公因数呢
不知道，但可以上网查找
zhenjen 发表于 2023-6-6 11:36
不知道，但可以上网查找
网上找不到我才问的，chatgpt 回答的也是 O(N^2) 算法。
时间复杂度要求是o（n）？
zhenjen 发表于 2023-6-6 11:40
时间复杂度要求是o（n）？
是的，因为你看，1 <= n <= 1000000，但是 1 <= a_i <= 1000000，可以根据这一条下手
n是数据范围，那a_i是什么？
zhenjen 发表于 2023-6-6 11:42
n是数据范围，那a_i是什么？
n 是数组长度，a_i 表示 a 的任一元素
n是长度，a是数字？
zhenjen 发表于 2023-6-6 11:44
n是长度，a是数字？
n 是长度，a 是一个数组，a_i 表示 a 的第 i 个元素，在这里可能不太清晰，这个意思就是，a 的所有元素都大于等于 1，小于等于 1000000
时间复杂度没有要求。
zhenjen 发表于 2023-6-6 11:46
时间复杂度没有要求。
时间复杂度自己想，想一想怎样的时间复杂度才能在 1s 以内通过此题。
zhangjinxuan 发表于 2023-6-6 11:47
时间复杂度自己想，想一想怎样的时间复杂度才能在 1s 以内通过此题。
我推荐看下找最大子区间的算法.算法时间复杂有on
zhenjen 发表于 2023-6-6 11:56
我推荐看下找最大子区间的算法.算法时间复杂有on
但是这里还有最大公因数，只有求和都会做嗷。
顶
顶
顶
maybe，可以分治？我不会，你可以试试要求GPT写出O(n)复杂度的代码
yinda_peng 发表于 2023-6-8 20:53
maybe，可以分治？我不会，你可以试试要求GPT写出O(n)复杂度的代码
分治{:10_257:}
说详细点呢？说个“也许”有点半对不对的感觉。
我问了 GPT 的，大多都是 O(n^2)