解説
解説
の各桁を下位桁から順に処理します。繰り上がりを表す変数 を用意し、初期値を とします。
先頭の桁を除き、現在の桁の数字を とすると、
- が偶数なら、 で割る操作を 回行う。
- が奇数なら、 を足してから で割る操作を行うため、操作回数は 回となる。
いずれの場合も、処理後の繰り上がりは
となります。
先頭の桁に到達した時点で、整数の値は です。 ならば、さらに で割る操作が 回必要です。
以上の処理を各 に対して行い、操作回数を合計すればよいです。
各桁を 回ずつ処理するため、時間計算量は です。
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。