CF Round #653 B - Multiply by 2, divide by 6


Tags:cpcodeforcesdiv3math

問題

https://codeforces.com/contest/1374/problem/B

問題文

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

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

制約

  • 1t2×1041 \le t \le 2 \times 10^4
  • 1n1091 \le n \le 10^9

サンプル

7
1
2
3
12
12345
15116544
387420489
0
-1
2
-1
-1
12
36

考察

問題の言い換え

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

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

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

解法

z1,x>yz \ne 1, x > y なら不可能。

そうではないなら、 xx に 1 を足し続けて、 x=yx = y にして、 x,yx, y から 1 を引き続けるのが最適。
その回数は、 (yx)+y(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;
}