1324 - Nhân 2 chia 6

Nếu số nguyên n của chúng ta bao gồm các thừa số nguyên tố khác 2 và 3 thì đáp án luôn là -1 (vì dù chúng ta có nhân 2 chia 3 đến đâu thì n cũng không thể được giảm xuống 1 được).

Ngược lại, gọi cnt2 là số lượng số 2 trong phép phân tích thừa số nguyên của n, tương tự cnt3 với số 3. Nếu cnt2 > cnt3, đáp án là -1 vì chúng ta không bao giờ có thể loại bỏ hết số 2 đi. Ngược lại, đáp án là (cnt3 - cnt2) + cnt3.

Độ phức tạp: O(log_n)

Mã nguồn tham khảo:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t, n;
    cin >> t;
    while(t--) {
        cin >> n;
        int cnt2 = 0, cnt3 = 0;

        // Đếm số lượng thừa số 2 và 3 trong n
        while(n % 2 == 0 || n % 3 == 0) {
            if(n % 2 == 0) {
                cnt2++;
                n /= 2;
            }
            if(n % 3 == 0) {
                cnt3++;
                n /= 3;
            }
        }

        // Kiểm tra xem n có phải là một số lẻ hay không
        if(n == 1 && cnt2 <= cnt3) {
            cout << 2 * cnt3 - cnt2 << "\n";
        } else {
            cout << -1 << "\n";
        }
    }
    return 0;
}