yukicoder：No.915 Plus Or Multiple Operation

問題

https://yukicoder.me/problems/no/915

解法

まず C が 1 であるときはクッキーを増やすことが出来ないので，答えは -1 となる．そうでないときは必ず A 枚まで増やすことが出来る．

操作を逆に考え，A 枚あるクッキーを 0 枚まで減らすことを考える．今ある枚数を t とおく．t が C で割り切れるときは C で割るのが良い．そうでないとき，t を C で割った余りだけ引く方法と，t を C - 1 ずつひたすら引いていく方法の 2 通りが考えられる．一応前者の操作を t に施しておき，後者での全体の操作回数を答えの候補として持っておく．t が 0 になったとき，答えの候補の中の min が操作回数の min であるので，この回数 * B を出力すればよい．全体で O(Q*log_C(A)) ぐらい．

解答

https://yukicoder.me/submissions/393939