1085B.md (1581B)
1 Source: https://codeforces.com/problemset/problem/1085/B 2 3 B. Div Times Mod 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Vasya likes to solve equations. Today he wants to solve $(x~\mathrm{div}~k) \cdot (x \bmod k) = n$, where $\mathrm{div}$ and $\mathrm{mod}$ stand for integer division and modulo operations (refer to the Notes below for exact definition). In this equation, $k$ and $n$ are positive integer parameters, and $x$ is a positive integer unknown. If there are several solutions, Vasya wants to find the smallest possible $x$. Can you help him? 22 23 Input 24 25 The first line contains two integers $n$ and $k$ ($1 \leq n \leq 10^6$, $2 \leq k \leq 1000$). 26 27 Output 28 29 Print a single integer $x$ — the smallest positive integer solution to $(x~\mathrm{div}~k) \cdot (x \bmod k) = n$. It is guaranteed that this equation has at least one positive integer solution. 30 31 Examples 32 33 Input 34 35 ``` 36 6 3 37 ``` 38 39 Output 40 41 ``` 42 11 43 ``` 44 45 Input 46 47 ``` 48 1 2 49 ``` 50 51 Output 52 53 ``` 54 3 55 ``` 56 57 Input 58 59 ``` 60 4 6 61 ``` 62 63 Output 64 65 ``` 66 10 67 ``` 68 69 Note 70 71 The result of integer division $a~\mathrm{div}~b$ is equal to the largest integer $c$ such that $b \cdot c \leq a$. $a$ modulo $b$ (shortened $a \bmod b$) is the only integer $c$ such that $0 \leq c \lt b$, and $a - c$ is divisible by $b$. 72 73 In the first sample, $11~\mathrm{div}~3 = 3$ and $11 \bmod 3 = 2$. Since $3 \cdot 2 = 6$, then $x = 11$ is a solution to $(x~\mathrm{div}~3) \cdot (x \bmod 3) = 6$. One can see that $19$ is the only other positive integer solution, hence $11$ is the smallest one.