codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.