AOJ 1310 : Find the Multiples

整数論

Find the Multiples | Aizu Online Judge

問題概要

  • N個の要素からなる数列Aが与えられます。
  • 各要素は0~9です。
  • [i,j] における数列を１つの数字と見た時 Qの倍数になるような
    iとjの組み合わせはいくつあるでしょう。

解法

  • 後ろから累積和っぽく区間 S[i,N-1] mod Q を取っていく。
  • i 番目から左に S[ l, i ] mod Q = 0となるような l はいくつあるか答えるには
    ( S[ l, 0 ] - S[ i+1, 0 ] ) / (k:10^(桁数+1)) = 0 ( mod Q )
    が分かれば良い。
  • 上を式変形すると
    S[ l, 0 ] = S[ i + 1, 0 ] ( mod Q )
    となるので、S[i+1,0] を探す問題になる。
  • これはmapなどを使えばOK
  • ここで問題があって k : は 10 の累乗なので 10 が Q で割りきれてしまうと計算がうまくいかない。
  • 素数で 10 % Q = 0 となるとな Q = 2, 5 の場合なので
    Q = 2, 5 の場合は別で処理する。（これは簡単）
ソースコード

感想

練習では後ろから累積和すら思いつかなかった。
寝る前に思いついてしまったので書いてみたが、何故かWAが大量に生えて寝れなくなる。

Q = 2,5 がダメというのはこういうものに慣れていないと気付けない。互いに素は危険。覚えた。