算法

(数学) $O(log\,n)$

题意：

给定一个数字，你有两个操作：一个是给目前的数字乘$2$，一个是给目前的数字除以$6$。问最少多少次就可以把给定的数字变换为$1$，如果不能变为$1$，那就输出$-1$。

解法：

注意到操作只能消除因子$2$和$3$，所以如果目前数字因子同时有$2$和$3$那就可以直接除以$6$同时消除，如果只剩下因子$3$，那么就可以乘$2$除以$6$达到消除因子$3$的目的，否则就无法操作，输出$-1$。

具体细节：

统计出$n$含多少个因子$2$，记为$c2$，再统计出$n$含多少个因子$3$，记为$c3$。如果$n$不含除了$2$和$3$以外的因子，并且$c2 <= c3$，那么答案是$c3 - c2 + c3$，否则答案是$-1$。

C++ 代码

#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        int c2 = 0, c3 = 0;
        while (n % 2 == 0) {
            n /= 2;
            c2++;
        }
        while (n % 3 == 0) {
            n /= 3;
            c3++;
        }
        if (n == 1 && c2 <= c3) cout << 2 * c3 - c2 << '\n';
        else cout << -1 << '\n';
    }

    return 0;
}