← 返回题目列表

Codeforces · 1985/B

B. 最大多重和

中文机器翻译题面 查看原题

给定一个整数 $$$n$$$,找到一个整数 $$$x$$$ 使得:

- $$$2 \leq x \leq n$$$。
- 小于或等于 $$$n$$$ 的 $$$x$$$ 的倍数之和被最大化。形式上, $$$x + 2x + 3x + \dots + kx$$$ 其中 $$$kx \leq n$$$ 在 $$$x$$$ 的所有可能值上最大化。

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。

每个测试用例包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$)。

输出

对于每个测试用例,输出一个整数,$$$x$$$ 的最优值。可以证明只有一个唯一的答案。

示例

输入 #1

2
3
15

输出 #1

3
2

注意

对于 $$$n = 3$$$,$$$x$$$ 的可能值为 $$$2$$$ 和 $$$3$$$。 $$$2$$$ 小于或等于 $$$n$$$ 的所有倍数之和仅为 $$$2$$$,而 $$$3$$$ 小于或等于 $$$n$$$ 的所有倍数之和为 $$$3$$$。因此,$$$3$$$ 是 $$$x$$$ 的最优值。

对于 $$$n = 15$$$,$$$x$$$ 的最佳值为 $$$2$$$。 $$$2$$$ 小于或等于 $$$n$$$ 的所有倍数之和为 $$$2 + 4 + 6 + 8 + 10 + 12 + 14 = 56$$$,可以证明它是 $$$x$$$ 的所有其他可能值中的最大值。