mayoko’s diary

プロコンとかいろいろ。

SRM 478 div1 easy: CarrotJumping

解法

8x+7 と 4x+3 ですが, 8x+7 = 2(4x+3)+1 です。
また, 4x+3 = 2(2x+1)+1 です。つまり, これらの数は, すべて 2x+1 という式を元につくられています。

init に init = 2*init+1 という操作を繰り返して, init%MOD == 0 となったとします。これまでに行った操作を x 回とすると,
・ x == 1 だと, 4x+3, 8x+7 では表せない操作をしているので, スルー(更に多い回数の操作が必要となる)
・ x > 1 なら, (x+2)/3 を計算することで 4x+3, 8x+7 を使う最小操作回数がわかる(よくわかりませんが小さい数で試すとそうなるので多分正しい)
が答えです。

int MOD = 1e9+7;

class CarrotJumping {
public:
    int theJump(int init) {
        for (int i = 0; i <= 3*100000; i++) {
            if (init%MOD == 0) {
                if (i != 1) return (i+2)/3;
            }
            init = (init*2+1) % MOD;
        }
        return -1;
    }
};