[Codeforces] Educational Codeforces Round 66 (Div. 2) A. From Hero to Zero

問題

方針

正の整数 \( n \) に対して、次の二つの操作を\( n \) が \( 0 \) になるまで行います。

  1. \( n \) から \( 1 \) を引く
  2. 正の整数 \( k \) が \( n \) を割ることができるとき、\( n \) を \( k \) で割る

このときの最小の操作回数を求めるには、2. の操作を行える時は行い、そうではないとき、1. の操作を行います。1. の操作を連続して行う回数は、\( n \bmod k \) です。このとき、\( n = n – n \bmod k \) となり、\( n – n \bmod k \) は \( k \) で割ることができます。

コード