题意理解

我们有三个整数：

• $l$：可以开始测量的最早时间（整点）
• $r$：可以开始测量的最晚时间（整点）
• $a$：星球自转周期（小时）

要求选择两个时间 $i, j$ 满足：

1. $l \le i < j \le r$
2. $j - i$ 是 $a$ 的倍数

问有多少对 $(i, j)$。

思路分析

条件 $j - i$ 是 $a$ 的倍数 意味着：

$j = i + k \cdot a$ 其中 $k \ge 1$，且 $j \le r$。

所以对于每个 $i$，满足条件的 $j$ 的个数为： $ \text{count}(i) = \left\lfloor \frac{r - i}{a} \right\rfloor $ 因为 $k$ 最小是 1，最大是 $\frac{r-i}{a}$ 向下取整。

数学化简

我们要求： $ S = \sum_{i=l}^{r-1} \left\lfloor \frac{r - i}{a} \right\rfloor $ 令 $x = r - i$，当 $i = l$ 时 $x = r - l$，当 $i = r-1$ 时 $x = 1$。

所以： $ S = \sum_{x=1}^{r-l} \left\lfloor \frac{x}{a} \right\rfloor $

快速计算 $\sum_{x=1}^{n} \lfloor x/a \rfloor$

设 $n = r - l$。

对于 $a > n$：显然和为 0（因为所有 $\lfloor x/a \rfloor = 0$）。

对于 $a \le n$：

$ \sum_{x=1}^{n} \left\lfloor \frac{x}{a} \right\rfloor = \sum_{k=1}^{\lfloor n/a \rfloor} \sum_{x=1}^{n} [\lfloor x/a \rfloor = k] $ 对于固定的 $k$，满足 $\lfloor x/a \rfloor = k$ 的 $x$ 范围是 $ka \le x \le \min(n, ka + a - 1)$，个数为： $\min(n, ka + a - 1) - ka + 1$ 但更简单的方法是：

$ \sum_{x=1}^{n} \lfloor x/a \rfloor = a \cdot \frac{m(m-1)}{2} + m \cdot (n - ma + 1) $ 其中 $m = \lfloor n/a \rfloor$。

解释：

• 对于商 $1, 2, \dots, m-1$，每个商出现 $a$ 次。
• 商 $m$ 出现 $n - ma + 1$ 次。

所以： $ S = a \cdot \frac{m(m-1)}{2} + m \cdot (n - ma + 1) $ 其中 $m = \lfloor \frac{r-l}{a} \rfloor$，$n = r-l$。

最终公式

$ \text{ans} = \begin{cases} 0, & \text{if } a > n \\ a \cdot \frac{m(m-1)}{2} + m \cdot (n - m a + 1), & \text{otherwise} \end{cases} $ 其中 $n = r - l$，$m = \lfloor n/a \rfloor$。

代码实现

#include <iostream>
using namespace std;

int main() {
    long long l, r, a;
    cin >> l >> r >> a;
    
    long long n = r - l;
    if (a > n) {
        cout << 0 << endl;
        return 0;
    }
    
    long long m = n / a;
    long long ans = a * m * (m - 1) / 2 + m * (n - m * a + 1);
    cout << ans << endl;
    
    return 0;
}

复杂度

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

样例验证

样例 1

l=1, r=5, a=2
n = 4
a <= n → m = 4/2 = 2
ans = 2*2*1/2 + 2*(4 - 2*2 + 1) = 2 + 2*(1) = 4
输出 4 ✓

样例 2

l=4, r=9, a=6
n = 5
a > n → 输出 0 ✓