Đếm số ≤ N vừa là bình phương hoàn hảo vừa là lập phương hoàn hảo C++

Cho số N. Đếm các số từ 1 đến N vừa là bình phương hoàn hảo (square) vừa là lập phương hoàn hảo (cube).

Quan sát toán học

Số vừa là bình phương vừa là lập phương ⇔ số là lũy thừa bậc 6 (vì LCM(2,3)=6).

Các số dạng: 1⁶=1, 2⁶=64, 3⁶=729, 4⁶=4096, 5⁶=15625, ...

Ví dụ minh họa

Ví dụ 1:

• Input: N = 100
• Output: 2
• Giải thích: 1 và 64.

Ví dụ 2:

• Input: N = 5000
• Output: 3
• Giải thích: 1, 64, 4096.

Mã nguồn C++ (Cách 1: Kiểm tra sqrt và cbrt)

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

int getCount(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (floor(sqrt(i)) == ceil(sqrt(i))) {        // Là bình phương
            if (floor(cbrt(i)) == ceil(cbrt(i))) {    // Là lập phương
                count++;
            }
        }
    }
    return count;
}

int main() {
    int N = 100;
    cout << "So luong so <= " << N << " la binh phuong va lap phuong: " << getCount(N);
    return 0;
}

Mã nguồn tối ưu O(1) - Tính trực tiếp

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

int getCountOptimized(int n) {
    // Số lượng số k⁶ ≤ n là floor(n^(1/6))
    return floor(pow(n, 1.0/6.0));
}

int main() {
    int N = 5000;
    cout << "So luong (toi uu): " << getCountOptimized(N);
    return 0;
}

Kết quả chạy chương trình

So luong so <= 100 la binh phuong va lap phuong: 2

Độ phức tạp

Lưu ý

• Hàm cbrt() tính căn bậc 3 (C++11).
• Phép tính pow(n, 1.0/6.0) có thể bị sai do độ chính xác float với N rất lớn. An toàn hơn dùng vòng lặp kiểm tra i⁶ ≤ N.