No.3360 Integer Parts of Integer Multiples of a Square Root
p-adic
hamamuProblem Statement
You are given positive integers $N, M$.
First, we introduce a term. A positive integer $n$ is called a good positive integer if $n$ is not the integer part of a positive integer multiple of $\sqrt{N}$, that is, if there does not exist a positive integer $m$ satisfying the following.
- The largest integer less than or equal to $m \sqrt{N}$ is $n$.
Determine whether there exist $M$ or more good positive integers, and if they exist, find the $M$-th smallest good positive integer.
Input
The input is given from standard input in $1$ line in the following format:
- The $1$st line contains $N, M$ separated by a single-byte space.
$N$ $M$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^{12}$.
- $M$ is an integer satisfying $1 \leq M \leq 10^6$.
Output
If there exist $M$ or more good positive integers, print the $M$-th smallest good positive integer on the $1$st line; otherwise, print NaN on the $1$st line.
Print a newline at the end.
Sample
Sample 1
Input
1 1
Output
NaN
We have $\sqrt{N} = 1$. Since every positive integer is a positive integer multiple of $1$, no good positive integer exists.
Sample 2
Input
2 1
Output
3
$\displaystyle \begin{array}{rcl} \displaystyle 1 \sqrt{N} &\displaystyle = &\displaystyle \textcolor{red}{1}.414 \ldots \\ \displaystyle 2 \sqrt{N} &\displaystyle = &\displaystyle \textcolor{red}{2}.828 \ldots \\ \displaystyle 3 \sqrt{N} &\displaystyle = &\displaystyle \textcolor{red}{4}.242 \ldots \end{array} $
Therefore, $3$ is the smallest good positive integer.
Sample 3
Input
4 2
Output
3
We have $\sqrt{N} = 2$, and the positive integers that can be represented as a positive integer multiple of $2$ are exactly the positive even numbers. Therefore, the good positive integers are exactly the positive odd numbers, and the $2$nd smallest odd number is $3$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。