题解说明

问题描述：
给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$，要求在所有长度 $\geq k$ 的子数组中，找到最大值：

$$\max \big( \gcd(\text{子数组}) \times \text{SUM}(\text{子数组}) \big) $$

其中 $\gcd(\text{子数组})$ 表示子数组所有元素的最大公约数，$\text{SUM}(\text{子数组})$ 表示子数组元素和。

核心思路：
$1.$ 前缀和：

• 用 $pre[i]$ 表示前 $i$ 个元素的和，方便 $O(1)$ 求任意子数组和。

$2.$ 单调栈维护 $\gcd$ 分段：

• 从右往左枚举子数组起点 $i$。
• 每次将 $a[i]$ 入栈，表示新区间 $[i,i]$。
• 向前合并：对栈中已有区间的 $\gcd$ 与 $a[i]$ 取 $\gcd$，若 $\gcd$ 发生变化则更新。
• 合并后去重：相邻区间若 $\gcd$ 相同，只保留最后一个。

这样栈中存储的是一系列区间，每个区间对应一个唯一的 $\gcd$ 值，且这些 $\gcd$ 值严格递减。

$3.$ 枚举区间贡献：

• 对栈中每个区间 $[i, S[j].second]$，若长度 $\geq k$，则计算：$$val = \gcd \times \big(pre[S[j].second] - pre[i-1]\big) $$
• 更新全局最大值 $Ans$。

算法流程：
$1.$ 输入 $n, k$ 和数组 $a$。
$2.$ 计算前缀和 $pre$。
$3.$ 初始化空栈 $S$，从右往左遍历 $i=n..1$：

• 将 $a[i]$ 入栈。
• 合并更新栈中区间的 $\gcd$。
• 去除重复 $\gcd$ 区间。
• 遍历栈中区间，若长度 $\geq k$，更新答案。
  $4.$ 输出 $Ans$。

复杂度分析：

• 每个元素最多被合并 $O(\log A)$ 次（$A$ 为数组元素大小），因为 $\gcd$ 值严格递减。
• 总复杂度 $O(n \log A)$，适合 $n \leq 10^6$ 的数据范围。
• 空间复杂度 $O(n)$。

实现细节与注意点：

• 使用 $long\ long$ 存储前缀和与答案，避免溢出。
• 栈中存储 $pair\{ \gcd\ 值,\ 区间右端点 \}$。
• 合并时要注意去重，避免重复计算。

总结：
该算法利用“前缀和 $+$ $\gcd$ 分段栈”的技巧，将所有可能的子数组 $\gcd$ 压缩为 $O(\log A)$ 个候选值，从而高效地计算最大 $\gcd \times

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int a[1000010];         // 存储输入的数组元素
LL pre[1000010];        // 前缀和数组，pre[i] = a[1] + a[2] + ... + a[i]
pair<int, int> S[1000010];  // 栈结构，存储{当前区间的GCD值, 区间右端点}
int main() {
    ios::sync_with_stdio(0);  // 关闭输入输出同步，加速cin/cout
    cin.tie(0);               // 解除cin与cout的绑定，进一步加速输入
    int n, k;
    cin >> n >> k;            // 读入数组长度n和子数组最小长度k

    // 读入数组元素并计算前缀和
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];  // 前缀和公式：pre[i] = pre[i-1] + a[i]
    }

    int tot = 0;              // 栈S的元素数量（栈顶指针）
    LL Ans = 0;               // 存储最终答案（最大GCD*子数组和）

    // 从后往前遍历数组，枚举子数组的起点i
    for (int i = n; i >= 1; -- i) {
        // 将当前元素a[i]作为新的区间起点，加入栈中（区间为[i,i]）
        S[++ tot] = {a[i], i};
        int wt = tot;         // 记录需要合并的起始位置

        // 从栈顶向前合并区间：计算当前元素与栈中已有区间的GCD
        for (int j = tot - 1; j >= 1; -- j) {
            // 计算栈中第j个区间的GCD与当前元素a[i]的GCD
            int tmp = __gcd(S[j].first, a[i]);
            wt = j;           // 更新合并起始位置

            // 若新GCD与原区间GCD相等，无需继续合并，跳出循环
            if (tmp == S[j].first)
                break;
            else
                // 否则更新栈中第j个区间的GCD为新值
                S[j].first = tmp;
        }

        int nt = wt;          // 合并后栈的新长度（临时指针）

        // 去除合并后栈中连续重复的GCD区间（保留最后一个）
        for (int j = wt + 1; j <= tot; ++ j) {
            // 若当前区间GCD与前一个不同，则保留
            if (S[j].first != S[j - 1].first) {
                S[++ nt] = S[j];
            }
        }

        tot = nt;             // 更新栈的实际长度

        // 遍历栈中所有区间，计算符合条件的子数组的价值
        for (int j = 1; j <= tot; ++ j) {
            // 检查区间长度是否满足 >=k（区间为[i, S[j].second]）
            if (S[j].second - i + 1 >= k) {
                // 计算当前区间的价值：GCD * 子数组和（利用前缀和快速计算）
                // 子数组和 = pre[S[j].second] - pre[i-1]
                Ans = max(Ans, 1ll * S[j].first * (pre[S[j].second] - pre[i - 1]));
            }
        }
    }

    cout << Ans << endl;      // 输出最大价值
    return 0;
}