Codeforces 813B The Golden Age，数学生成与间隔计算的解题之道

Codeforces 813B The Golden Age的解题核心是数学生成与间隔计算的结合，题目给定a、b、x、y，需生成所有a^p和b^q（p、q≥0）的数，在区间[L,R]中找到未被这些数覆盖的最长连续整数段，解题步骤为：先生成所有不超过R的a^p和b^q，去重后排序；再计算相邻生成数间的间隔、L到首个生成数的间隔、最后一个生成数到R的间隔；取最大间隔即为答案，该方法通过高效生成数列并分析间隔，精准解决区间未覆盖最长段问题。

Codeforces 813B（The Golden Age）是一道聚焦数学生成与区间间隔分析的编程题，题目要求在给定区间[l, r]内，找出由a的幂次（a^x，x≥0）和b的幂次（b^y，y≥0）组成的所有数，然后计算这些数在区间内形成的最大间隔——包括第一个数之前、相邻数之间、最后一个数之后的间隔。

核心思路

解决这道题的关键在于三步：生成幂次数集→筛选有效数→计算最大间隔。

生成幂次数集

由于r可能达到1e18,需用64位整数（如C++的long long）存储，并避免溢出：

• 对a的幂次：从1开始，每次乘a，直到当前值 > r/a（防止溢出），停止生成。
• 对b的幂次：同理处理，最终将所有幂次存入集合（自动去重）。

筛选有效数

从集合中筛选出落在[l, r]内的数，排序后得到有序数组。

计算最大间隔

• 空数组处理：若区间内无有效数，最大间隔为r - l + 1（整个区间都是间隔）。
• 非空数组处理：
  • 前间隔：第一个元素与l的差值（s[0] - l）。
  • 中间间隔：相邻元素差值减1（s[i] - s[i-1] -1）。
  • 后间隔：r与最后一个元素的差值（r - s.back()）。
  • 取上述间隔的最大值作为结果。

具体实现细节

幂次生成示例（C++）

set<long long> get_pows(long long base, long long r) {
    set<long long> res;
    if (base == 1) { // 特殊处理：1的幂次只有1
        res.insert(1);
        return res;
    }
    long long current = 1;
    while (true) {
        res.insert(current);
        if (current > r / base) break; // 防止溢出
        current *= base;
    }
    return res;
}

间隔计算示例

long long max_gap = 0;
vector<long long> nums;
// 筛选nums：从集合中取[l, r]内的数
if (nums.empty()) {
    max_gap = r - l + 1;
} else {
    max_gap = nums[0] - l;
    for (int i = 1; i < nums.size(); ++i) {
        max_gap = max(max_gap, nums[i] - nums[i-1] -1);
    }
    max_gap = max(max_gap, r - nums.back());
}

示例分析

假设输入：l=1, r=10, a=2, b=3

• 生成的幂次：{1,2,3,4,8,9}
• 筛选后数组：[1,2,3,4,8,9]
• 间隔计算：
  • 前间隔：1-1=0
  • 中间间隔：2-1-1=0,3-2-1=0,4-3-1=0,8-4-1=3,9-8-1=0
  • 后间隔：10-9=1
• 最大间隔：3

注意事项

1. 处理1的幂次：当a或b为1时，幂次仅为1，避免无限循环。
2. 溢出防范：乘base前需判断current > r/base，防止溢出。
3. 边界条件：区间内无有效数时，直接返回r-l+1。

Codeforces 813B通过简单的数学生成和间隔分析，考察了边界处理与溢出防范能力，由于幂次增长极快，生成的数数量极少，算法效率极高，掌握这些细节后，即可轻松解决这道题。