B. Maximum Multiple Sum 详细题解

题目重述

给定整数 $n$（$2 \le n \le 100$），选择一个整数 $x$ 满足 $2 \le x \le n$，使得所有不超过 $n$ 的 $x$ 的倍数的和 $S(x) = x + 2x + 3x + \dots + kx$（其中 $k = \lfloor n/x \rfloor$）最大。输出使 $S(x)$ 最大的 $x$（可以证明答案唯一）。

核心思路

由于 $n$ 很小（最多 $100$），可以直接枚举所有可能的 $x$，计算对应的 $S(x)$，然后找出最大值对应的 $x$。时间复杂度 $O(n^2)$ 完全可行。

算法步骤

1. 读入测试用例数 $t$。
2. 对于每个测试用例：
   • 读入整数 $n$。
   • 初始化 $best\_x = 2$，$best\_sum = 0$。
   • 对于 $x$ 从 $2$ 到 $n$：
     • 计算 $S = 0$。
     • 对于 $i = x, 2x, 3x, \dots$，只要 $i \le n$，累加 $S \leftarrow S + i$。
     • 如果 $S > best\_sum$，则更新 $best\_sum = S$，$best\_x = x$。
   • 输出 $best\_x$。

数学优化（可选）

注意到倍数和可以写成算术级数：

$$S(x) = x \cdot \frac{k(k+1)}{2}, \quad k = \left\lfloor \frac{n}{x} \right\rfloor. $$

因此可以在 $O(1)$ 内计算每个 $x$ 的和，避免内层循环。对于 $n \le 100$，两种写法均可。

复杂度分析

• 枚举法：外层循环 $O(n)$，内层循环 $O(n/x)$，总复杂度 $O(n \log n)$，对于 $n \le 100$ 非常快。
• 使用公式法：每个测试用例 $O(n)$。
• 总复杂度 $O(t \cdot n)$，$t \le 100$，$n \le 100$，完全满足。

正确性证明

• 因为 $n$ 是有限整数，$x$ 的取值只有有限个，枚举所有可能并比较和的大小必然能找到最大值。
• 题目保证答案唯一，因此直接输出即可。

示例验证

• $n=3$：枚举 $x=2$ 得 $S=2$，$x=3$ 得 $S=3$，最大值对应 $x=3$，输出 $3$。
• $n=15$：$x=2$ 得 $S=56$，$x=3$ 得 $45$，$x=4$ 得 $24$，…，$x=15$ 得 $15$，最大值对应 $x=2$，输出 $2$。与样例一致。

总结

本题是一个简单的枚举问题，利用 $n$ 很小的特点，直接计算每个 $x$ 的倍数和并比较大小即可。也可通过算术级数公式优化计算。最终输出使和最大的 $x$。