题解：P10403 「XSOI-R1」跳跃游戏

· · 题解

前言

这是我第一次写题解，因为其他大佬的题解实在是没看懂，所以自己写一篇讲一下我的思路。

思路

不难发现，\gcd 有一个性质：如果 [x, y] 的 \gcd 为 g，那么任何 [x, z] (x ≤ y ≤ z) 的 \gcd ≤ g。\ 也就是说，\gcd 随区间右端点增加不会突然变小后再变大 → 单调性→二分查找可行。

  1. 用 st 表预处理区间 \gcd，实现 O(1) 查询；
  2. 对每个左端点 x，通过二分找到所有 \gcd 不变的连续区间[x,y]；
  3. 针对 \gcd 为 2 或 3 的区间，分别计算符合奇偶条件的长度总和；
  4. 累加所有贡献得到答案；

对于通过二分找到所有 \gcd 不变的连续区间 [x,y]， 我们可以分段二分，二分查找分段区间 \gcd 不变的右端点 y，如下图所示：

一次二分确定一段 [pos, y]，这段区间 \gcd 都是相同的，然后更新 \gcd，继续找下一段。

AC代码

#include <bits/stdc++.h>
using namespace std;
int n, a[600086], st[600086][20], lg[600086];
long long ans;

// 预处理st表
void build() {
    // 预处理log2
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i >> 1] + 1;

    // st表初始化
    for (int i = 1; i <= n; i++)
        st[i][0] = a[i];

    // 递推ST表
    for (int j = 1; j <= lg[n]; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            st[i][j] = __gcd(st[i + (1 << (j - 1))][j - 1], st[i][j - 1]);
    }
}

// 区间gcd的O(1)查询
int get_gcd(int l, int r) {
    int j = lg[r - l + 1];
    return __gcd(st[l][j], st[r - (1 << j) + 1][j]);
}

// 计算区间[l, r]内所有偶数的和
long long ou_sum(int l, int r) {
    if (l > r)
        return 0;
    int first;
    if (l % 2 == 0)  // 起点是偶数
        first = l;
    else
        first = l + 1;
    if (first > r)
        return 0;
    int back;
    if (r % 2 == 0)  // 终点是偶数
        back = r;
    else
        back = r - 1;
    int count = (back - first) / 2 + 1;            // 项数
    return (long long)(first + back) * count / 2;  // 高斯求和
}

// 计算区间[l, r]内所有奇数的和
long long ji_sum(int l, int r) {
    if (l > r)
        return 0;
    int first;
    if (l % 2 == 1)  // 起点是奇数
        first = l;
    else
        first = l + 1;
    if (first > r)
        return 0;
    int back;
    if (r % 2 == 1)  // 终点是奇数
        back = r;
    else
        back = r - 1;
    int count = (back - first) / 2 + 1;
    return (long long)(first + back) * count / 2;  // 同上
}

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

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    build();

    // 枚举左端点x
    for (int x = 1; x <= n; x++) {
        int goal_gcd = a[x], pos = x;  // 当前区间的目标gcd（初始化为第一个数）和起始位置

        while (pos <= n) {
            int l = pos, r = n, y;

            // 二分查找：找到[x,y]的gcd等于goal_gcd的最远右端点y
            while (l <= r) {
                int mid = (l + r) / 2;
                if (get_gcd(x, mid) == goal_gcd) {
                    y = mid;      // 记录下来
                    l = mid + 1;  // 还能远
                } else
                    r = mid - 1;  // 太远了，往回走
            }

            // 根据gcd的值，累加对应区间贡献
            if (goal_gcd == 2) {
                // 分段区间gcd等于2，统计[x,y]的偶数和
                ans += ou_sum(pos - x + 1, y - x + 1);
            } else if (goal_gcd == 3) {
                // 分段区间gcd等于3，统计[x,y]的奇数和
                ans += ji_sum(pos - x + 1, y - x + 1);
            }

            // 如果已经到头，就结束
            if (y == n)
                break;

            // 否则，更新goal_gcd，并继续处理下一个分段区间
            goal_gcd = __gcd(goal_gcd, a[y + 1]);
            pos = y + 1;
        }
    }

    cout << ans;
    return 0;
}

因为 \gcd 每次只能下降，最多下降 \log A 次，所以时间复杂度：O(n \log A \log n)。\ 另外 st 表的预处理复杂度是 O(n \log n)，不会成为瓶颈。

如果有错误的话，感谢大家指正。