Editorial for power3: Lũy thừa bậc 3

Hiểu bài toán

Cho một số nguyên không âm N. Kiểm tra xem có tồn tại một số nguyên không âm x sao cho x³ = N hay không. N có thể lên tới 10¹⁸. Với mỗi test case, cần in ra YES nếu có, ngược lại in ra NO.

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

Cách Sử dụng hàm cbrt (Căn bậc ba)

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        // Tính căn bậc ba của n
        long long x = round(cbrt((long double)n));
        // Kiểm tra điều kiện
        if (x * x * x == n) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

• Time Complexity: O(1) mỗi test case
• Space Complexity: O(1)

Phương pháp này利用了C++11提供的 hàm cbrt để tính căn bậc ba của số thực. Do N có thể lên tới 10¹⁸, ta cần ép kiểu sang long double để tránh tràn số. Ta dùng round để làm tròn đến số nguyên gần nhất, sau đó kiểm tra xem lũy thừa bậc 3 của số nguyên đó có bằng N hay không. Đây là cách tiếp cận trực quan và ngắn gọn nhất.

Cách Tìm kiếm nhị phân (Binary Search)

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        long long l = 0, r = 2000000; // 2000000^3 > 10^18
        bool found = false;
        while (l <= r) {
            long long mid = l + (r - l) / 2;
            long long cube = mid * mid * mid;
            if (cube == n) {
                found = true;
                break;
            } else if (cube < n) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        cout << (found ? "YES" : "NO") << "\n";
    }
}

• Time Complexity: O(log(10^6)) ≈ O(1) mỗi test case
• Space Complexity: O(1)

Vì x³ = N, nên x không thể vượt quá ∛(10¹⁸) ≈ 10⁶. Ta có thể sử dụng tìm kiếm nhị phân trong khoảng [0, 2*10⁶] để tìm số x. Phương pháp này an toàn tuyệt đối về độ chính xác và không phụ thuộc vào hàm số thực.

Cách Kiểm tra lân cận

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        long long x = cbrt((long double)n);
        // Kiểm tra x và x+1 để xử lý lỗi làm tròn
        if (x * x * x == n || (x + 1) * (x + 1) * (x + 1) == n) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

• Time Complexity: O(1) mỗi test case
• Space Complexity: O(1)

Hàm cbrt trả về số thực, khi ép kiểu sang long long sẽ cắt bỏ phần thập phân. Nếu N là số chính phương, cbrt có thể trả về giá trị chính xác hoặc chênh lệch 1 đơn vị do lỗi làm tròn. Do đó, ta cần kiểm tra cả x và x+1 để đảm bảo chính xác.

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

Bài học kinh nghiệm

• N ≤ 10¹⁸ nên x ≤ 10⁶, số lượng x có thể khá nhỏ nên có thể sử dụng các phương pháp O(1) hoặc O(log N).
• Khi sử dụng số thực (float/double) để tính toán với số lớn, cần cẩn thận với độ chính xác (precision) và tràn số.
• Kiểm tra lân cận (x và x+1) là cách khắc phục hiệu quả lỗi làm tròn khi dùng hàm cbrt.

Lỗi thường gặp

• Sử dụng int hoặc long long để tính lũy thừa trước khi kiểm tra có thể gây tràn số nếu không kiểm tra biên.
• Quên ép kiểu sang long double khi dùng cbrt cho số lớn.
• Chỉ kiểm tra một giá trị x duy nhất sau khi dùng cbrt mà không kiểm tra các giá trị lân cận.