问题分析

我们需要找到制造至少 $n$ 台新机器人的最短时间。打印机的操作有两种：

• 扫描：花费 $a$ 小时，将当前所有机器人存入内存
• 打印：花费 $b$ 小时，从内存中打印一份当前军队的副本

关键是要找到最优的多阶段复制策略。

核心算法

算法框架：贪心分配 + 多阶段优化

将整个过程建模为 $i$ 个阶段，每个阶段包含一次扫描和若干次打印。目标是找到最优的阶段数 $i$ 和每个阶段的打印次数分配。

关键观察

1. 乘法增长：每个阶段将军队规模乘以某个因子
2. 总时间：$总时间 = i \times a + (\text{总打印次数}) \times b$
3. 平衡分配：各阶段的增长因子应该尽可能接近

算法步骤详解

1. 枚举阶段数

for (int i = 1; i <= 61; i++) {

枚举从 1 到 61 个阶段（因为 $2^{60} > 10^{18}$）。

2. 计算基础增长因子

int w = powl(n, 1. / i);

计算如果要达到目标 $n$，每个阶段平均需要的增长因子。

3. 贪心调整因子分配

multiset<int> s;
int u = 1;
for (int j = 1; j <= i; j++)
    s.insert(w), u *= w;

while (u < n) {
    auto w = *s.begin();
    s.erase(s.begin());
    u /= w;
    u *= (w + 1);
    s.insert(w + 1);
}

使用贪心策略调整各阶段的增长因子：

• 初始：所有阶段使用平均因子 $w$
• 调整：每次将最小的因子加 1，直到总乘积达到 $n$

4. 计算总时间

__int128 sum = 0;
for (auto x : s)
    sum += a + (__int128)(x - 1) * b;

每个阶段的时间 = $a$ (扫描) + $(x-1) \times b$ (打印)

算法标签

• 贪心算法 (Greedy Algorithm)
• 数论优化 (Number Theory Optimization)
• 多阶段决策 (Multi-stage Decision)
• 大数处理 (Big Number Handling)

复杂度分析

• 时间复杂度：$O(61 \times 61 \log 61) \approx O(20000)$
• 空间复杂度：$O(61)$

关键技巧

1. 阶段数上界

for (int i = 1; i <= 61; i++)

由于 $2^{60} > 10^{18}$，61 个阶段足够覆盖所有情况。

2. 贪心因子调整

使用 multiset 维护各阶段因子，每次增加最小因子来达到目标乘积。

3. 大数处理

__int128 sum = 0;

使用 __int128 避免整数溢出，因为总时间可能达到 $10^{18}$ 级别。

样例验证

样例1：n=8, a=2, b=1

• 最优解：2个阶段
• 阶段1：扫描1台 → 打印2次 → 得到3台（时间：2 + 2×1 = 4）
• 阶段2：扫描3台 → 打印2次 → 得到9台（时间：2 + 2×1 = 4）
• 总时间：8小时

算法计算过程：

对于 i=2：

• w = pow(9, 1/2) ≈ 3
• 初始：[3, 3]，乘积=9 ≥ 9
• 时间 = 2×a + (2+2)×b = 4 + 4 = 8

正确性证明

1. 完备性：枚举所有可能的阶段数（1-61），确保找到全局最优。

2. 最优性：贪心因子分配确保在给定阶段数下时间最小。

3. 可行性：每个阶段的增长因子对应实际的扫描-打印操作序列。

该解法通过巧妙的数学模型和贪心策略，将复杂的多阶段优化问题转化为可计算的形式，在常数时间内解决了这个大规模优化问题。