問題
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; }