No.25 有限小数

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 117
作問者 : yuki2006yuki2006
3 ProblemId : 70 / 出題時の順位表

問題文

peachは、分数で表された数が、有限小数で表されるかを知りたくなった。
「有限小数」とは \(1 / 8 = 0.125\) のような有限の小数で表される数値のことである。
\(4 / 3 = 1.33333\dots\) のような数は、有限の小数では表されないため該当しない。

ここで、\(64\)ビット符号付き整数で表される自然数が\(2\)つ\((N,M)\)与えられる。
この時 \(N/M\)が有限小数で表されるか判定してください。

有限小数で表される時、\(0\)でない一番小さい桁の数字を出力してください。
有限小数で表すことが出来ない時、\(-1\)を出力してください。

小数にならない時も、\(0\)でない一番小さい桁の数字を求めてください。

入力

N
M

\(1\)行目は、分数の分子を表す自然数\(N\ (1 \leq N \leq 9,223,372,036,854,775,807)\) が与えられます。
\(2\)行目は、分数の分母を表す自然数\(M\ (1 \leq M \leq 9,223,372,036,854,775,807)\) が与えられます。

出力

有限小数で表される時、\(0\)でない最後の数字を、
有限小数で表すことが出来ない時、\(-1\)を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
7
5
出力
4

\(7 / 5 = 1.4\) で有限小数で表すことができるので、最後の数は\(4\)となる。

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

\(2/3\)は有限小数で表すことが出来ないので\(-1\)となる。

サンプル3
入力
10
3
出力
-1

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

\(20/2\)は\(10\)になるが、\(0\)でない小さい位からみて最後の数なので\(1\)を出力する。

サンプル5
入力
12345
30517578125
出力
6

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。