📌 Tóm tắt đề bài

• Cho một số nguyên dương n \((1 \le n \le 10^0)\).
• Mỗi lần robot đọc a byte dữ liệu trong b giây với b ≥ 2, tức là chỉ được đọc số byte có dạng a^b với b ≥ 2.
• Robot có thể lặp lại quá trình đọc nhiều lần. Tổng số byte đọc phải bằng n.
• Yêu cầu: Tìm cách biểu diễn n thành tổng của các số có dạng a^b (b ≥ 2) sao cho tổng các số mũ b là nhỏ nhất.

🧩 Phân tích và ý tưởng

Bài toán là một dạng tổng lũy thừa có ràng buộc:

Biểu diễn \(n = a₁^{b₁} + a₂^{b₂} + ... + a_k^{b_k}\), với bᵢ ≥ 2, sao cho tổng b₁ + b₂ + ... + b_k là nhỏ nhất.

✅ Ý tưởng chiến lược

Ta lần lượt kiểm tra các biểu diễn của n từ đơn giản đến phức tạp theo số lượng và bậc của các lũy thừa:

1. Tổng mũ = 2:

   • \(n = a^2\)

2. Tổng mũ = 3:

   • \(n = a^3\)

3. Tổng mũ = 4:

   • \(n = a^2 + b^2\)

4. Tổng mũ = 5:

   • \(n = a^5\)
   • \(n = a^3 + b^2\)

5. Tổng mũ = 6:

   • \(n = a^3 + b^3\)
   • \(n = a^2 + b^2 + c^2\)

6. Tổng mũ = 7:

   • \(n = a^7\)
   • \(n = a^5 + b^2\)
   • \(n = a^3 + b^2 + c^2\)

7. Nếu không có biểu diễn nào ở trên thỏa mãn → trả về 8 (trường hợp xấu nhất).

🔍 Chi tiết kiểm tra

Sử dụng các hàm kiểm tra:

• check2(n): kiểm tra \(n\) là số chính phương.
• check3(n): kiểm tra \(n\) là số lập phương.
• check4(n): kiểm tra \(n = a^2 + b^2\)
• check5(n): kiểm tra \(n = a^5\) hoặc \(a^3 + b^2\)
• check6(n): kiểm tra \(n = a^3 + b^3\) hoặc \(a^2 + b^2 + c^2\)
• check7(n): kiểm tra \(n = a^7, a^5 + b^2\), hoặc \(a^3 + b^2 + c^2\)

Dừng tại trường hợp đầu tiên phù hợp, vì ta đang duyệt theo thứ tự tăng dần của tổng số mũ.

🧪 Ví dụ minh họa

Ví dụ 1:

Input:  n = 25

• 25 = 5² → mũ = 2 → kết quả: 2

Ví dụ 2:

Input: n = 35

• Không là chính phương, lập phương
• Nhưng: \(35 = 3^3 + 2^3\) → tổng mũ = \(3 + 3 = 6\) → kết quả: 6

Ví dụ 3:

Input: n = 60

• Không là bình phương, lập phương, không biểu diễn được dưới 4 số chính phương...
• Nhưng: \(60 = 2^3 + 4^2 + 6^2\) → tổng mũ = \(3 + 2 + 2 = 7\) → kết quả: 7

⏱️ Độ phức tạp

• Mỗi checkX(n) có độ phức tạp:
  • check2, check3: O(1)
  • check4: O(√n)
  • check5, check6, check7: Tối đa O(n^{1/k}) với k = 2..7
• Với giới hạn \(n \le 10^9\), tổng thời gian xử lý vẫn đảm bảo trong thời gian cho phép, nhờ:
  • Duyệt số mũ từ nhỏ tới lớn
  • Dừng sớm khi tìm được kết quả phù hợp
• Phù hợp cho xử lý nhiều test case (T ≤ 10⁵)

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

// Kiểm tra n có phải là bình phương
bool isSquare(int n) {
    int r = sqrt(n);
    return r * r == n;
}

// Kiểm tra n có phải là lập phương
bool isCube(int n) {
    int r = cbrt(n);
    return r * r * r == n;
}

// Kiểm tra n có thể viết thành tổng 2 bình phương
bool check2Squares(int n) {
    for (int i = 1; i * i <= n; ++i) {
        int remain = n - i * i;
        if (isSquare(remain)) return true;
    }
    return false;
}

// Kiểm tra n = a^5 hoặc a^3 + b^2
bool checkPower5OrCubePlusSquare(int n) {
    for (int i = 1; pow(i, 5) <= n; ++i)
        if (pow(i, 5) == n) return true;

    for (int i = 1; i * i * i <= n; ++i)
        if (isSquare(n - i * i * i)) return true;

    return false;
}

// Kiểm tra n = a^3 + b^3 hoặc a^2 + b^2 + c^2
bool checkTwoCubesOrThreeSquares(int n) {
    for (int i = 1; i * i * i <= n; ++i)
        if (isCube(n - i * i * i)) return true;

    for (int i = 1; i * i <= n; ++i) {
        int remain = n - i * i;
        for (int j = i; j * j <= remain; ++j)
            if (isSquare(remain - j * j)) return true;
    }

    return false;
}

// Kiểm tra n biểu diễn với tổng mũ = 7
bool checkPower7Mix(int n) {
    for (int i = 1; pow(i, 7) <= n; ++i)
        if (pow(i, 7) == n) return true;

    for (int i = 1; pow(i, 5) <= n; ++i)
        if (isSquare(n - pow(i, 5))) return true;

    for (int i = 1; i * i * i <= n; ++i)
        if (check2Squares(n - i * i * i)) return true;

    return false;
}

// Giải quyết một test case
int minimalExponentSum(int n) {
    if (isSquare(n)) return 2;
    if (isCube(n)) return 3;
    if (check2Squares(n)) return 4;
    if (checkPower5OrCubePlusSquare(n)) return 5;
    if (checkTwoCubesOrThreeSquares(n)) return 6;
    if (checkPower7Mix(n)) return 7;
    return 8;
}

int main() {
    // Tối ưu nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << minimalExponentSum(n) << '\n';
    }
    return 0;
}