[已解决]区间 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
我的意思是他都无法写正确

集如4

425放任

Addy945

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 1e6 + 5;
int a[MAXN];
ll pre[MAXN]; // 前缀和

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[i];
        pre[i] = pre[i - 1] + a[i];
    }

    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], r);

        // 合并前面的 GCD
        for (auto &p : cur) {
            int g = p.first;
            int l = p.second;
            int new_g = gcd(g, a[r]);
            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[r] - pre[l - 1];
            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;
}