题意分析

题目要求计算一个弹射器的总伤害。弹射器首次攻击造成伤害 $D$，第 $K$ 次攻击造成的伤害为 $\lceil D/K \rceil$（向上取整）。给定攻击次数 $N$，需要求出 $N$ 次攻击的总伤害。输入包含多个测试用例，每个用例为两个正整数 $D$ 和 $N$（$1 \leq D, N \leq 2 \times 10^9$），输入以两个 0 结束。输出每个测试用例的总伤害。

关键挑战：

• $D$ 和 $N$ 最大可达 $2 \times 10^9$，直接遍历 $K$ 从 1 到 $N$ 计算 $\lceil D/K \rceil$ 会超时（时间复杂度 $O(N)$）。
• 需要高效算法：利用数学转换和整除分块技术（也称为调和级数技巧），将问题转化为计算 $\lfloor (D-1)/K \rfloor$ 的和，将时间复杂度优化到 $O(\sqrt{D})$。

数学推导：

• $\lceil D/K \rceil = \lfloor (D-1)/K \rfloor + 1$（对于正整数 $D$ 和 $K$）。
• 总伤害 $S = \sum_{K=1}^{N} \lceil D/K \rceil = \sum_{K=1}^{N} \left( \lfloor (D-1)/K \rfloor + 1 \right) = \sum_{K=1}^{N} \lfloor (D-1)/K \rfloor + N$。
• 令 $M = D-1$：
  • 如果 $D = 1$，则 $M = 0$，$S = N$（因为每个 $\lceil 1/K \rceil = 1$）。
  • 如果 $D > 1$，则 $M \geq 1$，求和 $\sum_{K=1}^{N} \lfloor M/K \rfloor$ 只需计算到 $K = \min(N, M)$，因为在 $K > M$ 时，$\lfloor M/K \rfloor = 0$。

解题思路

1. 处理边界情况:
   • 如果 $D = 1$，直接返回 $N$。
   • 如果 $D > 1$，计算 $M = D - 1$ 和 $up = \min(N, M)$。
2. 整除分块计算和 $\sum_{K=1}^{up} \lfloor M/K \rfloor$:
   • 整除分块思想：$\lfloor M/K \rfloor$ 的值在多个连续的 $K$ 上相同，这些区间（块）可以快速枚举。
   • 算法步骤：
     • 初始化 $i = 1$ 和部分和 $T = 0$。
     • 当 $i \leq up$：
       • 计算 $v = \lfloor M/i \rfloor$（当前块的值）。
       • 计算块的右端点 $j = \min(\lfloor M / v \rfloor, up)$（此范围内 $\lfloor M/K \rfloor = v$）。
       • 计算块内元素个数 $count = j - i + 1$。
       • 累加块贡献 $T \leftarrow T + v \times count$。
       • 更新 $i = j + 1$ 处理下一个块。
   • 时间复杂度：$O(\sqrt{up})$，因为块数约为 $2\sqrt{up}$。对于 $up \leq 2 \times 10^9$，$\sqrt{up} \approx 44721$，高效可行。
3. 总伤害计算:
   • $S = T + N$。
4. 多测试用例处理：
   • 读取每个测试用例 $(D, N)$，直到遇到 $(0, 0)$。
   • 使用 long long 类型防止溢出（最大总伤害 $S \leq N \times D \leq 4 \times 10^{18}$，在 long long 范围内）。

C++ 代码实现

#include <iostream>
using namespace std;

long long computeTotal(long long D, long long N) {
    if (D == 1) {
        return N; // ceil(D/K)=1 for all K
    }
    long long M = D - 1;
    long long up = min(N, M); // Only sum K from 1 to min(N, M)
    long long T = 0;
    if (M > 0) {
        long long i = 1;
        while (i <= up) {
            long long v = M / i; // floor(M/i)
            long long j = min(M / v, up); // Right endpoint of the block
            long long count = j - i + 1; // Number of elements in block
            T += v * count; // Sum of this block
            i = j + 1; // Move to next block
        }
    }
    return T + N; // Total damage
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long D, N;
    while (cin >> D >> N) {
        if (D == 0 && N == 0) break;
        cout << computeTotal(D, N) << '\n';
    }
    return 0;
}