問題一覧 > 教育的問題

No.2271 平方根の13桁精度近似計算

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 19
作問者 : 👑 p-adicp-adic / テスター : 遭難者遭難者
0 ProblemId : 8608 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-14 22:43:28

問題文

入力に整数 NN と非負整数 EE が与えられます。

 

まずは用語の導入です。00 でない整数 nn に対し、v5(n)v_5(n) でその 55 進加法付値(nn55 で割り切れる回数)を表します。また整数 n0n_0n1n_1 に対し、その 55 進距離 d5(n0,n1)d_5(n_0,n_1) を次のように定めます:

d5(n0,n1)={5v5(n0n1)(n0n1)0(n0=n1)\displaystyle d_5(n_0,n_1) = \left\{ \begin{array}{ll} \displaystyle 5^{- v_5(n_0 - n_1)} &\displaystyle (n_0 \neq n_1) \\ \displaystyle 0 &\displaystyle (n_0 = n_1) \\ \end{array} \right.

整数 nn と非負整数 ee に対し、nn の 平方根の ee 桁精度 55 進近似値とは、d5(n,r2)5ed_5(n,r^2) \leq 5^{-e} を満たす整数 rr のことです。

 

229r229- 2^{29} \leq r \leq 2^{29} を満たす NN の平方根の EE 桁精度 55 進近似値 rr が存在するか否かを判定し、存在する場合はそのような rr11 つ求めてください。

入力

入力は次の形式で標準入力から与えられます:
NN
EE

制約

入力は以下の制約を満たします:

  • NN229N229- 2^{29} \leq N \leq 2^{29} を満たす整数
  • EE0E130 \leq E \leq 13 を満たす整数

出力

229r229- 2^{29} \leq r \leq 2^{29} を満たす NN の平方根の EE 桁精度 55 進近似値 rr が存在する場合はそのような rr11 つを 11 行に出力し、存在しない場合はNaNと出力してください。

ただしこの問題はスペシャルジャッジ問題です。正解となる出力は一意でないかもしれません。

最後に改行してください。

サンプル

サンプル1
入力
0
0
出力
0

d5(0,02)=01=50\displaystyle d_5(0,0^2) = 0 \leq 1 = 5^{-0}

であるので、0000 の平方根の 00 桁精度 55 進近似値です。

サンプル2
入力
1
1
出力
1

d5(1,12)=051\displaystyle d_5(1,1^2) = 0 \leq 5^{-1}

であるので、1111 の平方根の 11 桁精度 55 進近似値です。この他にも 1-166 などが正解となります。

サンプル3
入力
2
1
出力
NaN

22 の平方根の 11 桁精度 55 進近似値は存在しません。

サンプル4
入力
-1
1
出力
2

d5(1,22)=5v5(5)=51\displaystyle d_5(-1,2^2) = 5^{-v_5(-5)} = 5^{-1}

であるので、221-1 の平方根の 11 桁精度 55 進近似値です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。