ABC044-D：桁和 / Digit Sum

問題

https://beta.atcoder.jp/contests/abc044/tasks/arc060_b

整数 n に対して b 進数の桁和 f(b, n) が与えられる。f(b, n) = s を満たすような最小の b を求めよ。

制約

  • 1 \le n \le 10^{11}
  • 1 \le s \le 10^{11}

考え方

n が大きいので単純に全探索はできない。そこで \sqrt{n} で場合分けする。

(i) 2 \le b \le \sqrt{n} の場合

この場合は b で全探索が可能である。b を 2 から順番に参照し、桁和を求める関数 f の結果が s に等しい場合は、その b を出力すればいい。

(ii) b > \sqrt{n} の場合

この場合は p, q を用いて n = bp + q\ (p \lt b) と b 進数表示で表すことができる。また仮定より p + q = s である。

また n = bp + q \geq bp > p^2 より p \lt \sqrt{n} となる。

b = \displaystyle \frac{n-s}{p} + 1 より p を 0 \le p \lt \sqrt{n} の範囲で全探索して解を求めればよい。

Submission #2996291 - AtCoder Beginner Contest 044

どこに着目して考察するべきだったか

1 \le n \le 10^{11} の制約から O(N) は間に合わないが O(\sqrt{N}) は間に合う。また \sqrt{N} \le b では n = bp + q と b 進数で表すとシンプルな形になる。b は b = \displaystyle \frac{n-s}{p} + 1 と p に依存するので、p の範囲を定めるように式変形をすると全探索できる。

何がバグっていたか

得た知見

  • \sqrt{N} 以上の N の b 進数表示
  • 変域を制限する式変形

類題