题目描述

来自 $\text{Muzambaro}$ 星球的外星人再次选举了不受欢迎的领导人。他们计划用灯光装饰城市中的 $k$ 座摩天大楼。这些大楼位于 “$\text{The Deaf Street}$” 的一侧，共有 $n=high-low+1$ 座建筑，编号从 $low$ 到 $high$ ，相邻建筑距离相等。

需要选择 $k$ 座建筑满足：

1. 被选中的建筑编号构成等差数列（即等间距）
2. 这 $k$ 个编号的和能被 $k$ 整除

给定 $low$ 、 $high$ 和 $k$ ，求满足条件的方案数。

输入格式：多组数据，每行三个整数 $low$ , $high$ , $k$ ，以 0 0 0 结束。
输出格式：对于每组数据，输出 Case i: ans ，其中 $i$ 为测试序号， $ans$ 为答案。

题目分析

数学模型

设选择的建筑编号为等差数列： $a,a+d,a+2d,\dots ,a+(k-1)d$ ，其中：

• $a$ 为首项（首座建筑的编号）
• $d$ 为公差（建筑间距）
• 所有编号需在 $[low,high]$ 范围内

约束条件

1. 范围约束

由于 $a+(k-1)d\le high$ 且 $a\ge low$ ，可得：

• $d\le \frac{high-low}{k-1}$
• 对于给定的 $d$ ， $a$ 的取值范围为： $low\le a\le high-(k-1)d$

2. 整除约束

$k$ 个编号的和为：
$$S=\frac{k}{2}\left[2a+(k-1)d\right]$$
需要 $k\mid S$ ，即：
$$k\mid \frac{k}{2}\left[2a+(k-1)d\right]$$

分情况讨论：

• 当 $k$ 为奇数时： $\frac{k}{2}$ 不是整数，原条件等价于 $2\mid (k-1)d$
• 当 $k$ 为偶数时： $\frac{k}{2}$ 是整数，条件等价于 $2\mid \left[2a+(k-1)d\right]$ ，由于 $2a$ 是偶数，即 $2\mid (k-1)d$

合并条件：无论 $k$ 奇偶，都需要 $(k-1)d$ 是偶数。

方案数计算

对于每个合法的 $d$ （满足 $(k-1)d$ 是偶数且 $d\le \frac{high-low}{k-1}$ ），首项 $a$ 有：
$$cnt=\max (0,high-(k-1)d-low+1)$$
种选择。

总方案数为所有合法 $d$ 对应的 $cnt$ 之和。

特殊情况 $k=2$

当 $k=2$ 时，条件简化为 $d$ 必须是偶数（因为 $(2-1)d=d$ 需要是偶数）。此时：

• $d$ 的取值范围： $2,4,6,\dots ,high-low$
• 对于每个偶数 $d$ ，方案数： $high-d-low+1$

设 $n=high-low$ ，则方案数为：
$$\sum _{i=1}^{\lfloor n/2\rfloor }(n-2i+1)=\lfloor \frac{n}{2}\rfloor \times n-{\lfloor \frac{n}{2}\rfloor }^2$$
这是一个 $O(1)$ 的公式，避免了枚举。

算法设计

1. 对于 $k=2$ ：直接使用公式计算
2. 对于 $k>2$ ：枚举 $d$ 从 $1$ 到 $\frac{high-low}{k-1}$
   • 检查 $(k-1)d$ 是否为偶数
   • 计算 $cnt=high-(k-1)d-low+1$
   • 若 $cnt>0$ 则累加到答案

复杂度分析

• $k=2$ 时： $O(1)$
• $k>2$ 时：需要枚举 $d$ ，最坏情况 $k=3$ ， $d$ 最多 $\frac{high-low}{2}\approx 10^7$
• 题目保证输入不超过 $1001$ 行，最坏情况 $1000\times 10^7=10^{10}$ 次操作，但实际数据中 $k$ 通常较大，使得 $d$ 的范围很小，能够通过。

代码实现

// OOPS! They did it Again...
// UVa ID: 10799
// Verdict: Accepted
// Submission Date: 2025-12-13
// UVa Run Time: 0.000s
//
// 版权所有（C）2025，邱秋。metaphysis # yeah dot net

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

typedef long long ll;

// 计算 k=2 时的方案数
ll solveK2(ll low, ll high) {
    ll n = high - low;           // 注意：是 high-low，不是 high-low+1
    ll m = n / 2;                // 偶数 d 的个数
    return m * n - m * m;        // 等差数列求和公式
}

// 计算 k>2 时的方案数
ll solveK(ll low, ll high, ll k) {
    ll maxD = (high - low) / (k - 1);  // 最大公差
    ll ans = 0;
    
    for (ll d = 1; d <= maxD; ++d) {
        // 条件：(k-1)*d 必须是偶数
        if (((k - 1) * d) & 1) continue;
        
        ll cnt = high - (k - 1) * d - low + 1;
        if (cnt > 0) ans += cnt;
    }
    
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll low, high, k;
    int caseNo = 1;
    
    while (cin >> low >> high >> k) {
        if (low == 0 && high == 0 && k == 0) break;
        
        ll ans;
        if (k == 2) ans = solveK2(low, high);
        else ans = solveK(low, high, k);
        
        cout << "Case " << caseNo++ << ": " << ans << "\n";
    }
    
    return 0;
}

关键点总结

1. 数学推导是核心：正确理解等差数列求和与整除条件是解题关键
2. 注意边界情况： $k=2$ 时公式中的 $n$ 是 $high-low$ 而非 $high-low+1$
3. 优化策略：对于 $k=2$ 使用公式直接计算，避免枚举
4. 代码简洁性：直接枚举法在 $k>2$ 时足够高效，且避免了复杂边界处理

本题展示了如何将实际问题抽象为数学模型，并通过数学分析简化计算。正确的公式推导比复杂的算法优化更重要。