AOJ 5/27

2014-05-27 | [Competitive programming]

1298

よさそうな直線を適当に全部試したら通った．

1308

mod 2 で連立方程式の解の存在を確かめるだけ

1310

Q = 2, 5 の場合は明らか． それ以外の場合は，mod Q での 10 の逆元が存在することに注意する． ある境界をまたぐような数たちだけを考えると，境界より上の値を hi，境界より下の値を lo とすると hi * 10^(lo の桁数) + lo ≡ 0 (mod Q) ならよい． 変形すると，hi ≡ -lo / (10^(lo の桁数)) となる．右辺の値を lo に対して lo’ とよぶ． 境界から 1 つずつ進めていって，hi 及び lo’ の値を全部覚えておき，等しくする方法の数を数えると，その境界については解ける． あとは分割統治をすれば，O(N log^2 N) で解ける．