問題
https://codeforces.com/contest/1374/problem/B (新しいタブで開く)
問題文
整数 が与えられる。1 回の操作で、 に 2 をかけるか、 が 6 の倍数なら を 6 で割るか、どちらかをできる。
操作を行って、最終的に が 1 になるまでの最小回数は?
制約
サンプル
7
1
2
3
12
12345
15116544
387420489
0
-1
2
-1
-1
12
36
考察
問題の言い換え
素因数分解して、 と表すことにする。
このとき、問題は以下のように言い換えられる。
に 1 を足すか、 両方から 1 を引くか、どちらかを 1 回の操作でできる。
にするための最小回数は?
解法
なら不可能。
そうではないなら、 に 1 を足し続けて、 にして、 から 1 を引き続けるのが最適。
その回数は、 になる。
コード
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;
}