E. Insane Problem - 题解

比赛与标签

比赛: Codeforces Round 993 (Div. 4) 标签: binary search, greedy, implementation, math, number theory 难度: *1300

题目大意喵~

各位Master，下午好喵~！这道题呀，是给了我们五个整数 k, l1, r1, l2, r2。我们的任务是，找出有多少对萌萌的整数 (x, y)，能同时满足下面这三个条件呐：

x 的取值范围要在 [l1, r1] 之间。
y 的取值范围要在 [l2, r2] 之间。
存在一个非负整数 n，使得 y / x = k^n 成立。

简单来说，就是要找到在各自区间内的 x 和 y，使得 y 等于 x 乘以 k 的某个非负整数次幂。我们要做的就是数一数，到底有多少对这样的 (x, y) 呢？

解题思路分析喵！

刚看到这道题，x 和 y 的范围都可能很大（到 10^9 呢！），直接暴力枚举 x 和 y 的所有组合肯定是不行的，会超时超到天上去的，喵~。

所以，我们需要换个思路！题目的核心在于这个神奇的式子：y / x = k^n。让我们把它变个形，是不是就成了 y = x * k^n 啦？

看到这个式子，我们有三个变量 x, y, n。既然 x 和 y 的范围太大了，那我们能不能从 n 下手呢？ n 是一个非负整数，所以 k^n 的值会是 k^0=1, k^1=k, k^2, k^3... 这样一直增长下去。

因为 k >= 2，所以 k^n 增长得非常快！又因为 y <= r2，并且 x >= 1，所以我们能得到一个很重要的不等式：k^n <= x * k^n = y <= r2。这意味着 k^n 的值不会超过 r2。

这给了我们一个绝妙的启发！我们可以不去枚举 x 和 y，而是去枚举 k^n 的所有可能值！因为 k^n 呈指数级增长，所以它的可能取值其实非常少，完全在我们可以接受的范围内，喵~。

让我们来固定一个 k^n 的值，叫它 factor 吧。现在我们的任务就变成了：对于一个固定的 factor，有多少个 x 满足条件呢？

此时，y = x * factor。我们把这个关系代入 y 的取值范围限制中： l2 <= y <= r2 就变成了 l2 <= x * factor <= r2

从这个不等式中，我们可以解出 x 的新范围：

x * factor >= l2 => x >= l2 / factor。因为 x 是整数，所以 x 必须大于等于 l2 / factor 的上取整。在整数运算里，ceil(a/b) 可以用 (a + b - 1) / b 来计算，这是一个非常有用的技巧哦！
x * factor <= r2 => x <= r2 / factor。因为 x 是整数，所以 x 小于等于 r2 / factor 的下取整，也就是 r2 / factor 的整数除法结果。

这样，对于一个固定的 factor，我们就得到了一个由 y 推导出的 x 的范围：[(l2 + factor - 1) / factor, r2 / factor]。

别忘了，x 本身还有一个限制：l1 <= x <= r1。为了让 x 同时满足所有条件，它必须在这两个范围的交集里。两个区间的交集 [a, b] 和 [c, d] 是 [max(a, c), min(b, d)]。

所以，对于当前的 factor，x 的最终合法范围是：

下界 L = max(l1, (l2 + factor - 1) / factor)
上界 R = min(r1, r2 / factor)

如果 L <= R，说明存在合法的 x，数量就是 R - L + 1 个。我们把这个数量加到总答案里。如果 L > R，说明没有合法的 x，就不用加啦。

我们的算法流程就是：

初始化总答案 ans = 0。
初始化 factor = 1 (对应 n=0)。
进入一个循环，只要 factor 还在 r2 的承受范围之内： a. 计算出 x 的合法范围 [L, R]。 b. 如果 L <= R，就把 R - L + 1 加到 ans 上。 c. 更新 factor 为 factor * k，准备检查下一个 n 的情况。
循环结束后，ans 就是我们要求的答案啦！

一个小小的注意事项喵：factor 在乘以 k 的时候可能会溢出 long long 的范围。一个聪明的做法是，在乘法之前检查一下。如果 factor > r2 / k，那么下一次的 factor * k 肯定会大于 r2，也就没有继续循环的必要了，可以直接 break 掉，这样既安全又高效，的说！

代码实现！

cpp

#include <iostream>

using namespace std;

int main() {
    // 提高输入输出效率，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        long long k, l1, r1, l2, r2;
        cin >> k >> l1 >> r1 >> l2 >> r2;

        // factor 就是我们思路里提到的 k^n
        long long factor = 1;
        long long ans = 0;

        // 我们枚举 k^n 的所有可能值，直到它可能超过 y 的上界 r2
        while (factor <= r2) {
            // 根据 y = x * factor 和 l2 <= y <= r2，推导 x 的范围
            // low_bound 是 x 的下界，即 ceil(l2 / factor)
            long long low_bound = (l2 + factor - 1) / factor;
            // high_bound 是 x 的上界，即 floor(r2 / factor)
            long long high_bound = r2 / factor;

            // x 的最终范围是 [l1, r1] 和 [low_bound, high_bound] 的交集
            // L 是交集的下界
            long long L = max(l1, low_bound);
            // R 是交集的上界
            long long R = min(r1, high_bound);

            // 如果交集非空 (L <= R)，说明存在合法的 x
            if (L <= R) {
                // 那么对于当前的 factor，就有 (R - L + 1) 个合法的 x
                ans += (R - L + 1);
            }

            // 这是一个很重要的防溢出检查！
            // 如果当前的 factor 已经大于 r2/k，那么 factor * k 必然会大于 r2
            // 也就没有必要进行下一次循环了，提前结束可以避免溢出风险，喵~
            if (factor > r2 / k) {
                break;
            }

            // 更新 factor 到下一个 k 的幂次
            factor *= k;
        }

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

复杂度分析喵

时间复杂度: O(t * log_k(r2)) 的说。对于每个测试用例，我们循环的次数取决于 factor 从 1 增长到 r2 需要乘以多少次 k。这正是对数 log_k(r2) 的定义。因为有 t 个测试用例，所以总时间复杂度就是 O(t * log_k(r2))。这是一个非常快的速度哦！
空间复杂度: O(1) 的说。在每个测试用例中，我们只使用了几个 long long 类型的变量来存储中间值和结果，没有使用额外的数据结构，所以空间消耗是常数级别的。

知识点与总结

这道题虽然被叫做 "Insane Problem"，但只要我们冷静分析，找到正确的切入点，它就变得非常可爱了呢，喵~

核心思想 - 变换枚举对象: 这是解决本题的关键！当直接枚举目标（如 x 和 y）的范围过大时，尝试寻找一个与它们相关、但取值范围小得多的变量（如本题的 n 或 k^n）来进行枚举。这是一种非常经典且强大的优化思路。
数学技巧 - 整除与上取整: 在处理整型变量的除法时，a / b 默认是下取整。而计算上取整 ceil(a/b) 时，对于正整数 a 和 b， (a + b - 1) / b 是一个百试百灵的公式，Master一定要记住它呐！
编程技巧 - 防溢出: 在进行大数乘法时，要时刻警惕数据溢出的风险。像代码中 if (factor > r2 / k) 这样的预判，是保证代码健壮性的好习惯。它不仅防止了溢出，还顺便优化了不必要的循环。

总之，这道题完美地将数学思维和编程技巧结合在了一起。希望这篇题解能帮助到你，也希望Master在算法的世界里玩得开心，喵~！

E. Insane Problem - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路分析喵！ ​

代码实现！ ​

复杂度分析喵 ​

知识点与总结 ​