集体锻炼

形式化题目

给定长度为 $n$ 的序列 $a_1,\dots,a_n$ ，对每个连续区间 $[l,r]$ 定义价值为 $l \cdot r \cdot \gcd(a_l,\dots,a_r)$ ，求所有区间价值之和对 $998244353$ 取模的结果。

思路

直接枚举 $O(n^2)$ 个区间会超时，关键观察是：固定右端点 $r$ ，随着左端点向左扩展，区间 $\gcd$ 只会单调不增，且不同的 $\gcd$ 取值只有 $O(\log A)$ 种。

先看朴素的区间枚举：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:50
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const long long MOD = 998244353LL;
    int n;
    cin >> n;
    vector<int> values(n + 1);
    for (int i = 1; i <= n; i++) cin >> values[i];

    // 朴素做法：枚举所有区间 [left, right]，逐步向左扩展并更新 gcd
    long long answer = 0;
    for (int right = 1; right <= n; right++) {
        int current_gcd = 0;
        for (int left = right; left >= 1; left--) {
            current_gcd = gcd(current_gcd, values[left]);
            long long contribution = (long long)left * right % MOD;
            contribution = contribution * current_gcd % MOD;
            answer = (answer + contribution) % MOD;
        }
    }
    cout << answer << '\n';
    return 0;
}

按 gcd 分组

从左向右扫描，把右端点固定为 $r$ 。维护若干组 $(g, \sum l)$ ：组内所有区间都以 $r$ 结尾且 $\gcd$ 都等于 $g$ ， $\sum l$ 是这些区间左端点之和。

加入新元素 $a_r$ 后：

新单点区间 $[r,r]$ 的 $\gcd$ 是 $a_r$ ；
旧组的 $\gcd$ 变成 $\gcd(g, a_r)$ ；
相邻且 $\gcd$ 相同的组立即合并，保证每组 $\gcd$ 互不相同。

一组内所有区间的贡献一次算出：

g \times r \times \sum l \pmod{998244353}

复杂度来源

每个右端点处 gcd 不同的分组数量为 $O(\log \max a_i)$ ，因此总复杂度为 $O(n \log A)$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:50
 */
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353LL;

struct GcdGroup {
    int value;          // 一组区间共同的 gcd
    long long sum_left; // 这些区间左端点之和，用于一次统计贡献
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<GcdGroup> groups;
    vector<GcdGroup> next_groups;
    groups.reserve(32);
    next_groups.reserve(32);

    long long answer = 0;
    for (int right = 1; right <= n; right++) {
        int current;
        cin >> current;
        next_groups.clear();

        // 以 right 结尾的新单点区间 [right, right]
        GcdGroup single;
        single.value = current;
        single.sum_left = right;
        next_groups.push_back(single);

        // 旧区间左端点不变，gcd 与当前元素取 gcd 后放入新分组
        for (int i = 0; i < (int)groups.size(); i++) {
            GcdGroup group;
            group.value = gcd(groups[i].value, current);
            group.sum_left = groups[i].sum_left;
            // 相邻且 gcd 相同的组合并，保证每组的 gcd 互不相同
            if (!next_groups.empty() && next_groups.back().value == group.value) {
                next_groups.back().sum_left += group.sum_left;
                next_groups.back().sum_left %= MOD;
            } else {
                next_groups.push_back(group);
            }
        }

        groups.swap(next_groups);
        // 一组所有区间贡献为 gcd * right * (左端点之和)，一次性累加
        for (int i = 0; i < (int)groups.size(); i++) {
            long long contribution = (long long)groups[i].value * groups[i].sum_left % MOD;
            contribution = contribution * right % MOD;
            answer += contribution;
            answer %= MOD;
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

每个右端点维护的分组数为 $O(\log A)$ ，总时间复杂度 $O(n \log A)$ ，空间复杂度 $O(\log A)$ 。

总结

不要逐个区间重复计算 $\gcd$ 。把同一右端点下 $\gcd$ 相同的连续左端点合并成组，既保留了 $\gcd$ 值，又用左端点之和 $O(1)$ 处理整组贡献，这是这类区间统计题的经典优化。

子任务编号	分值	$n\le$	$a_i\le$
1	30	$1000$	$10^5$
2	20	$10^5$	$10$
3	30	$10^5$	$10^5$
4	20	$10^6$	$10^6$

目录

形式化题目

思路

按 gcd 分组

复杂度来源

代码

复杂度

总结