問題一覧 > 通常問題

No.25 有限小数

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 195
作問者 : yuki2006yuki2006
6 ProblemId : 70 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:49

問題文

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

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