Powerful Integers ใน C++

โจทย์

กำหนด 3 จำนวนเต็ม a, b, limit หาจำนวนเต็มทุกตัวในช่วง [1, limit] ที่เขียนในรูป a^i + b^j ได้ โดย i ≥ 0, j ≥ 0

ตัวอย่าง

a=2, b=5, limit=10

i=0,j=0: 2^0+5^0 = 1+1 = 2
i=1,j=0: 2^1+5^0 = 2+1 = 3
i=0,j=1: 2^0+5^1 = 1+5 = 6
i=1,j=1: 2^1+5^1 = 2+5 = 7
i=2,j=0: 2^2+5^0 = 4+1 = 5
i=3,j=0: 2^3+5^0 = 8+1 = 9

Result: [2, 3, 5, 6, 7, 9] (เรียงลำดับ, ไม่ซ้ำ)

แนวคิด: Nested Loops + Set

• วน i จนกว่า a^i > limit
• วน j จนกว่า b^j > limit
• ถ้า sum ≤ limit ใส่ Set (กันซ้ำ)
• กรณีพิเศษ: a=1 หรือ b=1 → พาวเวอร์คงที่ ต้อง break ไม่งั้น Infinite loop

โค้ด C++

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

vector<int> powerfulIntegers(int a, int b, int limit) {
    set<int> s; // ใช้ Set เพื่อ Unique + Sorted
    
    for (long long ai = 1; ai <= limit; ai *= a) {
        for (long long bj = 1; bj <= limit; bj *= b) {
            long long sum = ai + bj;
            if (sum <= limit) {
                s.insert((int)sum);
            } else {
                break; // bj มากเกินไปแล้ว
            }
            if (b == 1) break; // ป้องกัน Infinite loop
        }
        if (a == 1) break; // ป้องกัน Infinite loop
    }
    
    return vector<int>(s.begin(), s.end());
}

int main() {
    int a = 2, b = 5, limit = 10;
    vector<int> result = powerfulIntegers(a, b, limit);
    
    cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i + 1 < result.size()) cout << ", ";
    }
    cout << "]" << endl;
    
    // Test cases เพิ่ม
    auto print = [](int a, int b, int limit) {
        auto v = powerfulIntegers(a, b, limit);
        cout << "a=" << a << ", b=" << b << ", limit=" << limit << ": [";
        for (size_t i = 0; i < v.size(); i++) {
            cout << v[i] << (i+1

[2, 3, 5, 6, 7, 9]
a=2, b=5, limit=10: [2, 3, 5, 6, 7, 9]
a=3, b=5, limit=15: [2, 4, 6, 8, 10, 14]
a=1, b=2, limit=10: [2, 3, 5, 9]