概要

細胞数は操作 1 回ごとにちょうど 2 倍になるので、\(S\) から \(T\) に到達できるかを「\(T = S \times 2^n\) を満たす整数 \(n\) が存在するか」で判定し、存在するなら最小の \(n\) を求めます。

考察

「分裂促進」操作を \(n\) 回行うと、細胞数は必ず
$\(S \to 2S \to 4S \to \cdots \to S \times 2^n\)\( となります。つまり到達可能な値は **\)S\( に \)2^n$ を掛けたものだけ**です。

したがって目標 \(T\) にできる条件は次の 2 つです。

1. \(T\) が \(S\) の倍数であること（\(T = S \times q\) と書ける）
   
2. その比 \(q = \dfrac{T}{S}\) が \(2^n\)（2 のべき乗）であること

例えば \(S=3, T=24\) のとき、\(q=8=2^3\) なので 3 回で到達可能です。
一方 \(S=3, T=12\) なら \(q=4=2^2\) で 2 回。
\(S=3, T=18\) なら \(q=6\) は 2 のべき乗ではないため不可能です。

素朴に「\(S\) を 2 倍し続けて \(T\) になるか確認する」方法も考えられますが、数学的に条件が明確なので、割り算と「2 のべき乗判定」で確実に判定できます。さらに \(S,T\) は最大 \(10^{18}\) と大きいので、余計なループや計算を避けてシンプルに判断するのが安全です。

最後に、可能だとしても操作回数は最大 \(K\) 回までなので、求めた最小回数 \(n\) が \(n \le K\) を満たす必要があります。

アルゴリズム

1. \(T \bmod S \ne 0\) なら、\(T\) は \(S\) の倍数ではないので -1。
2. \(q = T / S\) を計算する。
3. \(q\) が 2 のべき乗か判定する。
   2 のべき乗（\(1,2,4,8,\dots\)）は二進数で 1000...0 の形なので、
   $\(q\ \&\ (q-1) = 0\)\( が成り立つ（ただし \)q>0$）。成り立たなければ -1。
4. \(q = 2^n\) のとき、\(n = \log_2 q\) が最小回数。これは bit_length() を使って
   $\(n = \text{bit\_length}(q) - 1\)$
   で求められる。
5. \(n \le K\) なら \(n\) を出力、そうでなければ -1。

計算量

• 時間計算量: \(O(1)\)
• 空間計算量: \(O(1)\)

実装のポイント

• まず \(T \% S\) を確認し、割り切れない場合は即 -1 にします（無駄な判定をしない）。

• 2 のべき乗判定は q & (q-1) を使うと高速かつ確実です（\(q=0\) にならないように \(q>0\) も確認）。

• 操作回数 \(n\) は q.bit_length() - 1 で求められます（\(q=1\) のとき \(n=0\) になり、操作不要のケースも正しく扱えます）。

  ソースコード

import sys

def main():
    S, T, K = map(int, sys.stdin.readline().split())

    if T % S != 0:
        print(-1)
        return

    q = T // S  # must be 2^n
    if q <= 0 or (q & (q - 1)) != 0:
        print(-1)
        return

    n = q.bit_length() - 1
    print(n if n <= K else -1)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。