水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Regular Contest 060 : D - 桁和 / Digit Sum

  • 問題

D - 桁和 / Digit Sum

10 進法で N を b 進法に直したとき、その桁和が S になるような最小の b を求める問題。

 

  • 解法

b をとりあえず 1~√N まで試す。b が √N を超えると、N の b 進法での桁数は2桁になるので、以下のような式が成り立つ。

N = αb + β (a, b <= √N)

この式での α + β = S が成り立つような b を求めればよい。

ここで、

α + β = S

β = S - α

なので、これを最初の式に代入して、

N = αb + (S - α)

N - S = (b - 1)α

となる。そうすれば、α を 1~√N の範囲で動かし、 b の最小値を取ればよい。

 

  • 解答

Submission #2715768 - AtCoder Regular Contest 060

f:id:babcs2035:20180623135728p:plain