我有了一个思路，但是懒得写代码了
首先，如果选择所有数，那么最终的结果就应该是 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:}
425放任
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e6 + 5;
int a;
ll pre; // 前缀和
int gcd(int a, int b) {
while (b) a %= b, swap(a, b);
return a;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a;
pre = pre + a;
}
ll best = -1;
int ansL = 1, ansR = 1;
vector<pair<int, int>> cur; // (gcd, l)
for (int r = 1; r <= n; ++r) {
vector<pair<int, int>> tmp;
tmp.emplace_back(a, r);
// 合并前面的 GCD
for (auto &p : cur) {
int g = p.first;
int l = p.second;
int new_g = gcd(g, a);
if (!tmp.empty() && tmp.back().first == new_g) continue;
tmp.emplace_back(new_g, l);
}
// 更新最优答案
for (auto &p : tmp) {
int g = p.first;
int l = p.second;
ll sum = pre - pre;
ll now = sum + g;
if (now > best) {
best = now;
ansL = l;
ansR = r;
}
}
cur.swap(tmp);
}
cout << ansL << " " << ansR << "\n";
cout << best << "\n";
return 0;
}