Số nguyên mạnh (Powerful Integers) trong C++

Cho 3 số nguyên a, b, limit. In các số trong khoảng [a, limit] dạng a^i + b^j (i≥0, j≥0).

Ví dụ

a=2, b=5, limit=10

Output: [2, 3, 4, 5, 6, 7, 9]

Giải thích: 2^0+5^0=2, 2^0+5^1=6, 2^1+5^0=3, 2^1+5^1=7, 2^2+5^0=5, 2^3+5^0=9

Cách tiếp cận: Brute force

• 2 vòng lặp lồng nhau duyệt đến limit
• Tính tổng a^i + b^j
• Nếu trong [a, limit] → lưu vào set (tránh trùng)
• Duyệt set in kết quả

Code C++

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

void powerfulNum(int a, int b, int limit) {
    set s;
    for (int i = 1; i < limit; i *= a) {
        for (int j = 1; j < limit; j *= b) {
            if (i + j <= limit) s.insert(i + j);
            else break;
            if (b == 1) break;
        }
        if (a == 1) break;
    }
    for (auto it : s) cout << it << " ";
}

int main() {
    int a = 2, b = 5, limit = 10;
    powerfulNum(a, b, limit);
    return 0;
}

Kết quả

2 3 5 6 7 9

Các powerful numbers trong [2,10]: 2, 3, 4, 6, 7, 9.