【アルゴリズム問題】yukicoder no.28 末尾最適化 (by くろとんさん) (level ☆☆☆☆)
閉じる
閉じる

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

×

【アルゴリズム問題】yukicoder no.28 末尾最適化 (by くろとんさん) (level ☆☆☆☆)

2014-09-22 00:25

    x[0] = seed

    x[n] = 1 + (x[n-1] ^ 2 + x[n-1] * 12345) % 100000009 (1<=n<=N)

    ※) %は剰余演算とする


    上の定義から作られるN+1個の要素を持つ数列xの中からK個数字を選びそれらを掛け合わせTとおく。

    TをB進数に変換した時末尾の0の数が最小となるTでは末尾の0の数はいくつになるか答えよ。


    例)

    B=18、Tが10進数で「612」ならTは18進数で「1g0」なので末尾の0の数は1個

    B=3、Tが10進数で「36」ならTは3進数で「1100」なので末尾の0の数は2個

    【Input】

    Q
    seed1 N1 K1 B1
    seed2 N2 K2 B2
    ...
    seedQ NQ KQ BQ
    ・1行目は Q(1<=Q<=1000)が与えられる。

    ・2行目からのQ行では seed(1<=seed<=100000009), N(1<=N<=10000), K(1<=K<=N+1), B(2<=B<=36) の組が与えられる。

    【Output】

    Q個の組ごとに末尾の0の数の最小を計算しそれぞれ出力せよ。ただし末尾に改行をつけること。


    【sample1】

    4
    98808561 8 6 18
    61316635 15 11 4
    37650646 100 86 20
    98630457 1000 647 2

    【ans1】

    1
    2
    6
    142


    1st. laycrs さん C++
    http://133.242.139.202/snowpack/yukicoder28/aAAqWExX

    2nd. なおさん C++
    http://133.242.139.202/snowpack/yukicoder28/ZDYEUWvf/

    3rd. scacheさん Java
    http://133.242.139.202/snowpack/yukicoder28/bIyeKa4T/

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