No.3360 平方根の整数倍の整数部分
タグ : / 解いたユーザー数 28
作問者 : 👑
p-adic
/ テスター :
hamamu
問題文
正整数 $N, M$ が与えられます。
まずは用語を導入します。正整数 $n$ が良い正整数であるとは、$n$ が $\sqrt{N}$ の正整数倍の整数部分でないこと、すなわち以下を満たす正整数 $m$ が存在しないということです。
- $m \sqrt{N}$ 以下の最大の整数は $n$ である。
良い正整数が $M$ 個以上存在するか否かを判定し、存在する場合は $M$ 番目に小さい良い正整数を求めてください。
入力
入力は以下の形式で標準入力から $1$ 行で与えられます：
- $1$ 行目に $N, M$ が半角空白区切りで与えられます。
$N$ $M$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^{12}$ を満たす整数である。
- $M$ は $1 \leq M \leq 10^6$ を満たす整数である。
出力
良い正整数が $M$ 個以上存在する場合は $M$ 番目に小さい良い正整数を $1$ 行目に出力し、存在しない場合はNaNと $1$ 行目に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1
出力
NaN
$\sqrt{N} = 1$ です。全ての正整数は $1$ の正整数倍であるため、良い正整数は存在しません。
サンプル2
入力
2 1
出力
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} $
より $3$ は最小の良い正整数です。
サンプル3
入力
4 2
出力
3
$\sqrt{N} = 2$ であり、$2$ の正整数倍で表せる正整数は正の偶数に他なりません。従って良い正整数は正の奇数に他ならず、$2$ 番目に小さい奇数は $3$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。