题解

题目要求统计满足以下条件的有序对 $(x, y)$ 的数量：

• $l_1 \le x \le r_1$
• $l_2 \le y \le r_2$
• 存在非负整数 $n$ 使得 $\frac{y}{x} = k^n$

直接枚举 $x$ 或 $y$ 的范围可达 $10^9$，显然不可行。但注意到指数 $n$ 的增长极快：即使 $k$ 取最小值 $2$，当 $n > 30$ 时 $2^{31} > 2 \times 10^9$（已超出坐标上限），所以实际有意义的 $n$ 只有 $O(\log_k 10^9)$ 个。由于 $k \ge 2$，最多枚举约 $32$ 个 $n$。

算法思路（区间求交）

固定 $n$ 后，条件变为 $y = x \cdot k^n$。我们需要 $x$ 同时满足：

• $l_1 \le x \le r_1$
• $l_2 \le x \cdot k^n \le r_2$

由第二个式子可得：

$$\left\lceil \frac{l_2}{k^n} \right\rceil \le x \le \left\lfloor \frac{r_2}{k^n} \right\rfloor $$

因为 $x$ 是整数。与第一个区间求交，得到 $x$ 的有效范围：

$$\max\left(l_1, \left\lceil \frac{l_2}{k^n} \right\rceil\right) \le x \le \min\left(r_1, \left\lfloor \frac{r_2}{k^n} \right\rfloor\right) $$

若该区间非空，则其中的每个整数 $x$ 都对应唯一的 $y = x \cdot k^n$，从而构成一个合法对。区间内的整数个数为：

$$\max\left(0, \min\left(r_1, \left\lfloor \frac{r_2}{k^n} \right\rfloor\right) - \max\left(l_1, \left\lceil \frac{l_2}{k^n} \right\rceil\right) + 1\right) $$

累加所有非负 $n$ 对应的计数即得答案。

实现细节与避免溢出

标程使用了巧妙的整数运算避免浮点误差和溢出：

1. 循环终止条件：r2/kn >= l1
   当 $k^n$ 不断增大，直到 $\frac{r_2}{k^n} < l_1$ 时，两个区间的交集一定为空，且更大的 $n$ 只会使 $\frac{r_2}{k^n}$ 更小，因此可以提前退出。

2. 上取整的无浮点实现：$\lceil \frac{l_2}{k^n} \rceil$ 用整数计算 (l2-1)/kn + 1 得到。这是因为当 $l_2$ 整除 $k^n$ 时，该式恰好等于 $\frac{l_2}{k^n}$；否则等于 $\lfloor \frac{l_2-1}{k^n} \rfloor + 1 = \lceil \frac{l_2}{k^n} \rceil$。

3. 防止溢出：kn 每次乘 $k$ 可能超出 long long 范围，但循环条件 r2/kn >= l1 自然限制了 kn 不会大到使除法结果小于 $l_1$，而 $r_2$ 最大 $10^9$，$k^n$ 最大约 $10^{18}$ 级别，long long 完全安全。同时计算区间内整数的公式中使用了 0ll 和 1ll 确保 long long 类型，结果直接加到 ans。

4. n=0 的特例：代码中 n=0 对应 $k^0 = 1$，此时条件为 $y = x$，只要两个区间有重叠即可统计，公式同样适用。

时间复杂度

每个测试用例枚举 $O(\log_k 10^9) \approx 30$ 个 $n$，每次 $O(1)$ 计算。总测试数 $t \le 10^4$，最坏计算量约 $3 \times 10^5$ 次操作，轻松通过。

C++ 参考代码（依据标程）

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--)
    {
        ll k, l1, r1, l2, r2;
        cin >> k >> l1 >> r1 >> l2 >> r2;
        ll kn = 1, ans = 0;
        for (int n = 0; r2 / kn >= l1; n++)
        {
            ans += max(0ll, min(r2 / kn, r1) - max((l2 - 1) / kn + 1, l1) + 1ll);
            kn *= k;
        }
        cout << ans << '\n';
    }
    return 0;
}