题目 B. ICPC Square 详细题解

问题重述

有 $N$ 层楼（编号 $1$ 到 $N$），电梯规则：从 $x$ 层可以到 $y$ 层当且仅当

• $y$ 是 $x$ 的倍数，且
• $y - x \le D$。

初始在 $S$ 层，可以乘坐零次或多次电梯，问能到达的最高楼层（不超过 $N$）。

关键观察

1. 可达楼层必为 $S$ 的倍数
   因为从 $S$ 出发，每次跳到的都是当前楼层的倍数，所以所有可达楼层都是 $S$ 的倍数。

2. 归一化
   将问题除以 $S$：令

   $$N' = \left\lfloor \frac{N}{S} \right\rfloor,\quad D' = \left\lfloor \frac{D}{S} \right\rfloor $$

   起始楼层变为 $1$，目标是在 $[1, N']$ 内从 $1$ 出发，每次可以跳到当前数 $x$ 的倍数 $y$ 且 $y - x \le D'$。
   最终答案乘以 $S$ 即可。

可达上界分析

设当前在 $x$，下一次跳到 $y = kx$（$k \ge 2$ 整数）。则增量

因此 $x \le y - x \le D'$，即 $x \le D'$。

结论：任何非自身的倍数跳跃，其起点必须 $\le D'$。

若想跳到较大的数 $Y$，它必须有一个真因子 $X$（$X < Y$）满足 $X \le D'$ 且 $Y - X \le D'$。
由于 $X \ge 1$，且 $Y$ 的最小真因子最大为 $Y/2$（当 $Y$ 为偶数时），所以

因此 $\frac{Y}{2} \le D'$，即 $Y \le 2D'$。

另外显然 $Y \le N'$。故能到达的楼层 不可能超过

能否到达 $Y_{\max}$ 的判断

令 $Y = Y_{\max}$。若 $Y = 0$（即 $D' = 0$ 且 $N' = 0$？实际上 $N' \ge 1$ 因为 $S \le N$），则起始楼层 $1$ 就是答案。下文假设 $Y \ge 1$。

情况 1：$Y$ 是偶数

取 $X = Y/2$，则

• $X$ 是整数且 $X \le D'$（因为 $Y \le 2D'$），
• 从 $1$ 可以直接跳到 $X$：$X$ 是 $1$ 的倍数且 $X-1 \le D'$ 成立（因 $X \le D' \le D'+1$），
• 从 $X$ 可以跳到 $Y$：$Y$ 是 $X$ 的倍数且 $Y-X = Y/2 \le D'$。
  因此 $Y$ 可达。

情况 2：$Y$ 是奇数

需要寻找一个真因子 $X$ 满足：

• $X \le D'$，
• $Y$ 是 $X$ 的倍数，
• $Y - X \le D'$。

由于 $Y$ 是奇数，其最小真因子 $X_{\min}$ 可能大于 $Y/2$？实际上奇数的最小真因子最大为 $Y/3$（例如 $9$ 的因子 $3$）。但更通用的方法是枚举 $Y$ 的所有因子 $X$（$X \ne Y$），检查是否 $X \le D'$ 且 $Y - X \le D'$。
因为 $Y \le 2D'$，所以 $Y - X \le D'$ 等价于 $X \ge Y - D'$。因此需要存在一个真因子 $X$ 满足

且 $X \mid Y$。

枚举 $Y$ 的所有因子可在 $O(\sqrt{Y})$ 时间内完成。若找到这样的 $X$，则 $Y$ 可达（从 $1$ 跳到 $X$，再跳到 $Y$）。若找不到，则 $Y$ 不可达。

不可达时的次优解

若 $Y$ 不可达，则 $Y-1$ 一定是偶数（因为 $Y$ 是奇数），且 $Y-1 \le 2D'$，故根据情况 1，$Y-1$ 可达。因此答案为 $Y-1$。

算法步骤

1. 读取 $N, D, S$。
2. 计算 $N' = \lfloor N/S \rfloor$，$D' = \lfloor D/S \rfloor$。
3. 若 $D' = 0$，则只能停留在 $1$，答案为 $S$。否则：
   • $Y = \min(2D',\ N')$。
   • 如果 $Y$ 是偶数，则 $ans = Y$。
   • 否则（$Y$ 奇数），枚举 $Y$ 的所有因子 $X$（$1 \le X \le \sqrt{Y}$），检查是否存在真因子 $X$ 满足 $Y-D' \le X \le D'$ 且 $X \mid Y$。
     • 若存在，则 $ans = Y$；
     • 否则 $ans = Y-1$。
4. 输出 $ans \times S$。

复杂度分析

• 归一化 $O(1)$。
• 枚举因子 $O(\sqrt{Y}) \le O(\sqrt{N})$，因为 $Y \le N' \le N/S \le N$。
• 总时间复杂度 $O(\sqrt{N})$，可轻松通过 $N \le 10^{12}$。

边界情况处理

• 当 $S > D$ 时，$D' = 0$，直接输出 $S$（只能停留在起点）。
• 当 $S = N$ 时，$N' = 1$，$Y = \min(2D',1)=1$，此时 $1$ 可达（起点本身），答案为 $S$，正确。
• 当 $Y=1$ 时（奇数），因子只有 $1$，检查 $1$ 是否在 $[Y-D', D']$ 内，即 $[1-D', D']$。由于 $D' \ge 1$，$1$ 满足，故 $Y$ 可达，答案正确。

参考代码（C++）

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

int main() {
    ll N, D, S;
    cin >> N >> D >> S;
    ll Np = N / S;
    ll Dp = D / S;
    if (Dp == 0) {
        cout << S << endl;
        return 0;
    }
    ll Y = min(2 * Dp, Np);
    if (Y % 2 == 0) {
        cout << Y * S << endl;
        return 0;
    }
    // Y is odd, check if reachable
    bool ok = false;
    for (ll x = 1; x * x <= Y; ++x) {
        if (Y % x == 0) {
            ll f1 = x, f2 = Y / x;
            if (f1 != Y && f1 >= Y - Dp && f1 <= Dp) ok = true;
            if (f2 != Y && f2 >= Y - Dp && f2 <= Dp) ok = true;
        }
    }
    if (ok) cout << Y * S << endl;
    else cout << (Y - 1) * S << endl;
    return 0;
}