← 返回题目列表

Codeforces · 1085/B

B. Div 时间 Mod

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

Vasya 喜欢解方程。今天他想求解$$$(x~\mathrm{div}~k) \cdot (x \bmod k) = n$$$,其中$$$\mathrm{div}$$$ 和$$$\mathrm{mod}$$$ 代表整数除法和模运算(具体定义请参阅下面的注释)。在该方程中,$$$k$$$和$$$n$$$是正整数参数,$$$x$$$是正整数未知数。如果有多个解决方案,Vasya 希望找到尽可能小的 $$$x$$$。你能帮助他吗?

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^6$$$, $$$2 \leq k \leq 1000$$$)。

输出

打印单个整数 $$$x$$$ — $$$(x~\mathrm{div}~k) \cdot (x \bmod k) = n$$$ 的最小正整数解。保证该方程至少有一个正整数解。

示例

输入 #1

6 3

输出 #1

11

输入 #2

1 2

输出 #2

3

输入 #3

4 6

输出 #3

10

注意

整数除法$$$a~\mathrm{div}~b$$$的结果等于最大整数$$$c$$$,使得$$$b \cdot c \leq a$$$。 $$$a$$$ 模 $$$b$$$(缩写为 $$$a \bmod b$$$)是唯一满足 $$$0 \leq c < b$$$ 的整数 $$$c$$$,且 $$$a - c$$$ 可被 $$$b$$$ 整除。

在第一个示例中,$$$11~\mathrm{div}~3 = 3$$$ 和 $$$11 \bmod 3 = 2$$$。由于 $$$3 \cdot 2 = 6$$$,那么 $$$x = 11$$$ 是 $$$(x~\mathrm{div}~3) \cdot (x \bmod 3) = 6$$$ 的解。可以看到 $$$19$$$ 是唯一的另一个正整数解,因此 $$$11$$$ 是最小的。