给一个正整数 \(n\) ，每一步可以让 \(n\) 除以 \(6\) 或者让 \(n\) 乘以 \(2\) 。询问进过多少次操作可以使得 \(n\) 变为 \(1\) 。或者回答不可能。
在唯一分解定理下观察 \(n\) 。
- 如果 \(n\) 除以 \(6\) ，则 \(2^{\alpha_1}3^{\alpha_2-1}\) 会变为 \(2^{\alpha_1-1}3^{\alpha_2-1}\) 。
- 如果 \(n\) 乘以 \(2\) ，则 \(2^{\alpha_1}\) 会变成 \(2^{\alpha_1+1}\) 。
于是若 \(n\) 存在 \(2, 3\) 以外的质因子则不能变为 \(1\) 。
若 \(\alpha_1 > \alpha_2\) 则不能变为 \(1\) 。
否则 \(n\) 能变为 \(1\) ，操作次数为 \(\alpha_2 + (\alpha_2 - \alpha_1)\)。
view
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
int n; std::cin >> n;
int cnt2 = 0, cnt3 = 0;
while (n % 2 == 0) {
cnt2 += 1;
n /= 2;
}
while (n % 3 == 0) {
cnt3 += 1;
n /= 3;
}
if (n > 1) std::cout << -1 << '\n';
else if (cnt2 > cnt3) std::cout << -1 << '\n';
else std::cout << cnt3 + (cnt3 - cnt2) << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while (_--) {solve();}
return 0;
}