B - Multiply by 2, divide by 6

問題

https://codeforces.com/contest/1374/problem/B (新しいタブで開く)

問題文

整数 $n$ が与えられる。1 回の操作で、 $n$ に 2 をかけるか、 $n$ が 6 の倍数なら $n$ を 6 で割るか、どちらかをできる。

操作を行って、最終的に $n$ が 1 になるまでの最小回数は？

制約

• $1 \le t \le 2 \times 10^4$
• $1 \le n \le 10^9$

サンプル

7
1
2
3
12
12345
15116544
387420489

0
-1
2
-1
-1
12
36

考察

問題の言い換え

素因数分解して、 $n = 2^x \cdot 3^y \cdot z$ と表すことにする。

このとき、問題は以下のように言い換えられる。

$x$ に 1 を足すか、 $x, y$ 両方から 1 を引くか、どちらかを 1 回の操作でできる。
$x = y = 0, z = 1$ にするための最小回数は？

解法

$z \ne 1, x > y$ なら不可能。

そうではないなら、 $x$ に 1 を足し続けて、 $x = y$ にして、 $x, y$ から 1 を引き続けるのが最適。
その回数は、 $(y - x) + y$ になる。

コード

https://codeforces.com/contest/1374/submission/126805401 (新しいタブで開く)

void solve() {
  int n;
  cin >> n;
  int ex2 = 0, ex3 = 0;
  for (int i = 2; i <= 3; i++) {
    if (n % i != 0) continue;
    int ex = 0;
    while (n % i == 0) {
      ex++;
      n /= i;
    }
    if (i == 2) ex2 = ex;
    if (i == 3) ex3 = ex;
  }
  if (n != 1 || ex2 > ex3) {
    cout << -1 << endl;
  }
  else {
    cout << (ex3 - ex2) + ex3 << endl;
  }
  return;
}