Hiểu bài toán

Bài toán yêu cầu kiểm tra một số thực N có phải là lũy thừa của 3 với số mũ k là số nguyên hay không. Nếu có, in ra giá trị k, ngược lại in ra 'NO'. Với N trong khoảng [0, 10^18] và sai số cho phép epsilon <= 10^-15.

Các cách tiếp cận

Cách Sử dụng Logarit và Làm tròn (Logarithmic Approach)

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
    long double N;
    cin >> N;

    if (N <= 0) {
        cout << "NO" << endl;
        return 0;
    }

    long double log_k = log10(N) / log10(3); // tính log3(N)
    long long k = llround(log_k);            // làm tròn về số nguyên

    long double power = pow(3.0L, k);        // 3^k
    if (fabsl(power - N) <= 1e-15) {
        cout << k << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Phương pháp này dựa vào tính chất logarit: Nếu N = 3^k thì log3(N) = k. Ta tính k = log10(N) / log10(3). Sau đó, ta làm tròn k về số nguyên gần nhất (llround). Cuối cùng, ta kiểm tra xem 3^k có bằng N trong khoảng sai số cho phép không. Nếu có, in ra k, ngược lại in 'NO'.

Cách Phương pháp Logarit với Kiểm tra Phân loại (Refined Logarithmic Approach)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
long double n;
 cin >> n;
 long double k = round(log10l(n) / log10l(3) * 1e16) / 1e16;
 if (n >= 1 && ceil(k) == floor(k))
      cout << int(k);
 else if (0 < n && n < 1 && k < 0)
      cout << k;
 else
      cout << "NO\n";
      return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Các giải pháp này cũng sử dụng logarit nhưng có kiểm tra điều kiện phức tạp hơn. Chúng tính k = log3(N) và kiểm tra nếu ceil(k) == floor(k) (tức là k là số nguyên) thì in ra. Tuy nhiên, cách xử lý các số âm (k < 0) và phân loại theo n >= 1 hoặc n < 1 là không cần thiết và có thể gây lỗi logic nếu k được tính toán sai lệch do làm tròn. Logic chính vẫn là tìm k sao cho 3^k ≈ N.

Cách Duyệt lũy thừa (Nếu N nhỏ)

// Pseudocode logic
long long p = 1;
int k = 0;
while(p <= N) {
    if (p == N) return k;
    p *= 3;
    k++;
}
return "NO";

• Time Complexity: O(log_3(N)) ~ O(38)
• Space Complexity: O(1)

Đối với N nhỏ (ví dụ N <= 10^18), ta có thể lặp từ 3^0, 3^1, ... tăng dần cho đến khi vượt quá N. Nếu tại bước nào đó giá trị bằng N thì trả về số mũ k. Phương pháp này chính xác tuyệt đối với số nguyên nhưng không phù hợp với số thực có sai số.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Sử dụng công thức logarit để chuyển bài toán kiểm tra lũy thừa thành bài toán kiểm tra số nguyên của chỉ số k.
• Cần sử dụng kiểu dữ liệu long double để đảm bảo độ chính xác cao nhất khi tính logarit và lũy thừa.
• Kiểm tra lại bằng cách tính ngược giá trị 3^k và so sánh chênh lệch với N trong khoảng sai số epsilon.

Lỗi thường gặp

• Lỗi làm tròn sai khi tính k từ logarit, dẫn đến việc chọn sai số mũ.
• Quên xử lý trường hợp N = 0 (vì log(0) vô nghĩa và 3^k không bao giờ bằng 0).
• Sử dụng sai kiểu dữ liệu (ví dụ: double thay vì long double) có thể gây sai số do mất mát bit khi tính toán với số lớn.