F. Maximum modulo equality - 题解

比赛与标签

比赛: Codeforces Round 991 (Div. 3) 标签: data structures, divide and conquer, math, number theory 难度: *1700

喵喵，这是什么任务呀？

主人你好呀！这道题是说，我们有一个数组 a 和很多个查询。每个查询会给我们一个区间 [l, r]。我们的任务呢，就是在这个区间里，找到一个最大的正整数 m，让区间里所有的数 a_l, a_{l+1}, ..., a_r 对 m 取余之后的结果都完全一样，也就是 a_l % m = a_{l+1} % m = ... = a_r % m 呐。

特别地，如果 m 可以是无限大的话（比如区间里只有一个数，或者所有数都相同），我们就输出 0。

举个栗子！如果区间是 [14, 2, 6]，我们可以找到 m=4。因为 14 % 4 = 2, 2 % 4 = 2, 6 % 4 = 2，余数都是 2，是不是很神奇的说！

来和咱一起分析吧！

初看这个问题，要在整个区间 [l, r] 里找到一个 m，感觉好复杂呀，要检查好多数字呢。别担心，让咱带你一步步把它变简单！

关键的数学转化！

这个问题的核心是 a_i % m = a_j % m。学过数论的小伙伴应该马上就反应过来了喵！这个式子等价于 (a_i - a_j) 能够被 m 整除，也就是 (a_i - a_j) % m = 0。

那么，要让整个区间 [l, r] 的所有数对 m 取余都相等，我们只需要保证相邻的两个数满足这个条件就行啦！为什么呢？因为模运算有传递性呀！如果 a_i % m = a_{i+1} % m 并且 a_{i+1} % m = a_{i+2} % m，那么自然就有 a_i % m = a_{i+2} % m。所以，我们只需要保证 a_i % m = a_{i+1} % m 对所有 i 从 l 到 r-1 都成立就可以啦！

好，现在问题变成了：找到一个最大的 m，使得 (a_i - a_{i+1}) % m = 0 对所有 i 从 l 到 r-1 都成立。因为 m 必须是正数，所以这等价于 m 必须是 |a_i - a_{i+1}| 的一个公约数。

要让 m 同时是 |a_l - a_{l+1}|, |a_{l+1} - a_{l+2}|, ..., |a_{r-1} - a_r| 的公约数，并且还要是最大的那个，喵哈哈，这不就是求这些差值的最大公约数 (GCD) 嘛！

最终的解题策略！

所以，我们的计划就很清晰了：

预处理：创建一个新的差分数组 b，其中 b[i] = |a[i+1] - a[i]|。
查询转化：对于每一个在原数组 a 上的查询 [l, r]，它就变成了在差分数组 b 上的一个区间查询 [l-1, r-2]（要注意下标的转换哦！）。我们需要计算 GCD(b[l-1], b[l], ..., b[r-2])。
高效查询：这是一个典型的静态数组区间查询问题。因为数组 b 一旦生成就不会再改变了，所以我们可以用我们最好的朋友——稀疏表 (Sparse Table, ST) 来解决！

稀疏表可以在 O(N log N) 的时间内完成预处理，然后用 O(1) 的惊人速度回答每一次区间 GCD 查询！完美符合题目的要求，的说！

看咱的代码魔法！

下面就是把我们的思路变成代码啦！咱已经加上了详细的注释，主人可以轻松看懂每一行是做什么的喵~

cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>

// 预先定义一个足够大的数组大小
const int MAX_N_Q = 200005;
// log_table 用于存储 log2 的值，是稀疏表查询O(1)的关键
int log_table[MAX_N_Q];

// 预计算 log2(i) 的整数部分，加速后续查询
void precompute_log() {
    log_table[1] = 0;
    for (int i = 2; i < MAX_N_Q; i++) {
        log_table[i] = log_table[i/2] + 1;
    }
}

void solve() {
    int n, q;
    std::cin >> n >> q;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 特殊情况：如果只有一个元素，任何查询的区间长度都是1
    if (n == 1) {
        for (int i = 0; i < q; ++i) {
            int l, r;
            std::cin >> l >> r;
            std::cout << 0 << " "; // m可以无限大，按题意输出0
        }
        std::cout << "\n";
        return;
    }

    // 步骤1: 创建差分数组b，大小为n-1
    std::vector<long long> b(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        b[i] = std::abs(a[i+1] - a[i]);
    }

    // 步骤2: 构建稀疏表(ST)来处理区间GCD查询
    int N = n - 1; // 差分数组的长度
    int K = log_table[N] + 1; // 稀疏表需要的列数
    std::vector<std::vector<long long>> st(N, std::vector<long long>(K));

    // 初始化稀疏表：长度为 2^0 = 1 的区间GCD就是其本身
    for (int i = 0; i < N; i++) {
        st[i][0] = b[i];
    }

    // 动态规划构建稀疏表
    // st[i][j] 表示从 b[i] 开始，长度为 2^j 的区间的GCD
    for (int j = 1; j < K; j++) {
        for (int i = 0; i + (1 << j) <= N; i++) {
            // 一个大区间的GCD等于它分裂成的两个小编区间的GCD
            st[i][j] = std::gcd(st[i][j-1], st[i + (1 << (j-1))][j-1]);
        }
    }

    // 定义一个查询函数，利用稀疏表O(1)计算区间GCD
    auto query_gcd = [&](int L, int R) {
        // k 是能覆盖 [L, R] 的最大 2 的幂次
        int j = log_table[R - L + 1];
        // 查询的区间 [L, R] 的GCD可以由两个有重叠的子区间 [L, L+2^j-1] 和 [R-2^j+1, R] 的GCD得到
        return std::gcd(st[L][j], st[R - (1 << j) + 1][j]);
    };

    // 步骤3: 处理所有查询
    for (int i = 0; i < q; ++i) {
        int l, r;
        std::cin >> l >> r;
        if (l == r) {
            // 区间只有一个数，m可以无限大，输出0
            std::cout << 0 << " ";
        } else {
            // 原数组a的查询区间是 [l, r] (1-based)
            // 对应到0-based数组a是 [l-1, r-1]
            // 对应到差分数组b是 [l-1, r-2]
            std::cout << query_gcd(l - 1, r - 2) << " ";
        }
    }
    std::cout << "\n";
}

int main() {
    // 加速输入输出，对付大数据量必备喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    precompute_log(); // 全局预计算一次log表
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

跑得快不快呀？

时间复杂度: O(N log N + Q) 的说。
- O(N) 用来计算差分数组 b。
- O(N log N) 用来构建稀疏表 st。
- O(Q) 用来回答 q 次查询，因为每次查询都是 O(1) 的！
- 所以总的时间复杂度就是预处理的 O(N log N) 加上查询的 O(Q)。对于这道题的数据范围来说，是飞快的！
空间复杂度: O(N log N) 的说。
- 主要的空间开销来自于我们的稀疏表 st，它是一个大小约为 N x log(N) 的二维数组。

这次又学到了什么呢？

这道题真是一次愉快的冒险，我们来总结一下宝藏吧！

数学转化是解题的魔法钥匙！将看似复杂的 a_i % m = a_j % m 条件，通过数论知识转化为更简单的 GCD(|a_i - a_{i+1}|, ...) 问题，是解题最关键的一步！
稀疏表 (Sparse Table) 是处理静态区间查询问题的超级英雄！特别是对于像 min, max, gcd 这种满足结合律和幂等性的操作，它能做到 O(N log N) 预处理，O(1) 查询，效率极高。
差分思想 的灵活运用。通过创建一个差分数组，我们成功地将原问题转化为了一个更经典的数据结构问题。
注意细节！比如 1-based 和 0-based 索引的转换，以及 l=r 这种边界情况的处理，都是写出AC代码不可或缺的部分哦！

希望这篇题解能帮到主人你，喵~！继续加油，算法的世界还有很多好玩的东西等着我们去探索呢！

F. Maximum modulo equality - 题解 ​

比赛与标签 ​

喵喵，这是什么任务呀？ ​

来和咱一起分析吧！ ​

关键的数学转化！ ​

最终的解题策略！ ​

看咱的代码魔法！ ​

跑得快不快呀？ ​

这次又学到了什么呢？ ​