【アルゴリズム問題】yukicoder no.25 有限小数(level ☆☆☆)
閉じる
閉じる

新しい記事を投稿しました。シェアして読者に伝えましょう

×

【アルゴリズム問題】yukicoder no.25 有限小数(level ☆☆☆)

2014-09-12 00:22
    peachは、分数で表された数が、有限小数で表されるかを知りたくなった。
    「有限小数」とは 1 / 8 =0.125 のような有限の小数で表される数値のことである。
    4/3=1.33333...のような数は、有限の小数では表されないため該当しない。

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

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

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

    (多倍長処理を使ったら、簡単にできることを見逃しておりました。)

    ヒント:約分・最大公約数・素因数分解

    【入力】
    N
    M

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

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

    【sample1】
    7
    5

    【ans1】
    4

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

    【sample2】
    2
    3

    【ans2】
    -1

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

    【sample3】
    10
    3

    【ans3】
    -1

    【sample4
    20
    2

    【ans4】
    1

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


    【sample5】
    12345
    30517578125

    【ans5】
    6

    【question】

    95367431640626
    95367431640625

    想定解
    http://ideone.com/G2nAaP

    1st . myonさん Haskell
    http://ideone.com/jBHufS

    2nd. なおさん C++
    http://ideone.com/asWuRH

    3rd. chokudaiさん C#
    http://ideone.com/sxJwRv


    広告
    コメントを書く
    コメントをするには、
    ログインして下さい。