← 返回题目列表

Codeforces · 1866/L

L. 利姆夫球

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

在工厂(Lihmuf Sorting)工作后,Lihmuf 想和他的好朋友 Pak Chanek 玩游戏。有 $$$N$$$ 个盒子,编号从 $$$1$$$ 到 $$$N$$$。第 $$$i$$$ 个盒子包含 $$$i$$$ 个球。 Pak Chanek 和 Lihmuf 将使用这些盒子玩游戏。

将会有 $$$N$$$ 回合,编号从 $$$1$$$ 到 $$$N$$$。在每一回合中,Pak Chanek 选择一个盒子并从该盒子中取出所有球,然后 Lihmuf 对他选择的一个盒子做同样的事情(有可能两个选择的盒子是相同的)。

给定一个整数$$$M$$$。在游戏开始之前,Lihmuf 必须选择一个满足 $$$1 \leq K \leq M$$$ 的整数 $$$K$$$。已知在第 $$$j$$$ 个回合中,Pak Chanek 将选择第 $$$j$$$ 个盒子,而 Lihmuf 将选择第 $$$y$$$ 个盒子,其中 $$$y=((j \times K - 1) \bmod N) + 1$$$。帮助 Lihmuf 选择正确的 $$$K$$$ 值,以便他获得尽可能多的球!如果 $$$K$$$ 的可能值有多个,导致球总数最多,请找到 $$$K$$$ 的最小此类值。

请记住,每个框都可以选择多次,但第一次选择框后,该框就会变空。

输入

唯一的一行包含两个整数 $$$N$$$ 和 $$$M$$$ ($$$1 \leq N \leq 10^9$$$; $$$1 \leq M \leq 2000$$$) — 盒子的数量和 $$$K$$$ 值的最大限制。

输出

一个整数,表示 $$$K$$$ 的值,这将使 Lihmuf 获得尽可能多的球。如果 $$$K$$$ 的可能值有多个,导致球总数最多,请找到 $$$K$$$ 的最小此类值。

示例

输入 #1

3 1

输出 #1

1

输入 #2

5 4

输出 #2

3

注意

在第一个例子中,如果 Lihmuf 选择 $$$K=1$$$,游戏将如下进行:

1. Pak Chanek 选择 $$$1$$$-st 盒子并获得 $$$1$$$ 球,然后 Lihmuf 选择 $$$1$$$-st 盒子并获得 $$$0$$$ 球。
2. Pak Chanek 选择 $$$2$$$-nd 盒子并获得 $$$2$$$ 球,然后 Lihmuf 选择 $$$2$$$-nd 盒子并获得 $$$0$$$ 球。
3. Pak Chanek 选择 $$$3$$$-rd 盒子并获得 $$$3$$$ 球,然后 Lihmuf 选择 $$$3$$$-rd 盒子并获得 $$$0$$$ 球。

Lihmuf 总共获得 $$$0+0+0=0$$$ 球。

Lihmuf 可以获得的最大球总数为 $$$0$$$,因为他只能选择 $$$K=1$$$。因此,$$$K=1$$$ 是导致最多球总数的 $$$K$$$ 的最小可能值。

在第二个例子中,如果 Lihmuf 选择 $$$K=3$$$,游戏将如下进行:

1. Pak Chanek 选择 $$$1$$$-st 盒子并获得 $$$1$$$ 球,然后 Lihmuf 选择 $$$3$$$-rd 盒子并获得 $$$3$$$ 球。
2. Pak Chanek 选择 $$$2$$$-nd 盒子并获得 $$$2$$$ 球,然后 Lihmuf 选择 $$$1$$$-st 盒子并获得 $$$0$$$ 球。
3. Pak Chanek 选择第 $$$3$$$ 个盒子并获得 $$$0$$$ 球,然后 Lihmuf 选择第 $$$4$$$ 个盒子并获得 $$$4$$$ 球。
4. Pak Chanek 选择第 $$$4$$$ 个盒子并获得 $$$0$$$ 球,然后 Lihmuf 选择第 $$$2$$$ 个盒子并获得 $$$0$$$ 球。
5. Pak Chanek 选择第 $$$5$$$ 个盒子并获得 $$$5$$$ 球,然后 Lihmuf 选择第 $$$5$$$ 个盒子并获得 $$$0$$$ 球。

Lihmuf 总共获得 $$$3+0+4+0+0=7$$$ 球。

可以得出,$$$7$$$ 是 Lihmuf 可以获得的最大总球数。导致 $$$7$$$ 球总数的 $$$K$$$ 的可能值为 $$$3$$$ 和 $$$4$$$。因此,$$$K=3$$$ 是$$$K$$$ 产生最多球总数的最小可能值。