Kiểm tra số có dạng x^y (x mũ y) C++

Kiểm tra số N có thể viết dưới dạng xʸ với x,y ≥ 2 nguyên.

Thuật toán

• Duyệt cơ số x từ 2 đến √N.
• Tính y = log(N)/log(x). Nếu y gần số nguyên → tìm thấy.
• Hoặc dùng lũy thừa nguyên: nhân dồn xᵏ cho đến khi ≥ N.

Chương trình C++ (cách lũy thừa nguyên - chính xác)

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

bool isPerfectPower(int n) {
    if (n <= 1) return true; // 1 = 1^y
    for (int x = 2; x*x <= n; x++) {
        long long p = x;
        while (p < n) {
            if (p > LLONG_MAX / x) break;
            p *= x;
        }
        if (p == n) return true;
    }
    return false;
}

int main() {
    vector test = {125, 91, 16, 27, 32, 64, 100, 1000, 1};
    for (int n : test)
        cout << n << ": " << (isPerfectPower(n) ? "Co dang x^y" : "Khong") << "\n";
    return 0;
}

Kết quả

125: Co dang x^y (5^3)
91: Khong
16: Co dang x^y (2^4, 4^2)
27: Co dang x^y (3^3)
32: Co dang x^y (2^5)
64: Co dang x^y (2^6, 4^3, 8^2)
100: Co dang x^y (10^2)
1000: Co dang x^y (10^3)
1: Co dang x^y