พิมพ์จำนวนเต็มที่เป็นผลรวมกำลังของสองตัวเลขใน C++

ภาพรวมปัญหา

ได้รับ a, b และ bound ต้องพิมพ์ค่าทั้งหมด < bound ที่เป็นผลรวมของ a^i + b^j

ตัวอย่าง

Input: a=2, b=3, bound=8
Output: 2 3 4 5 7

วิธีแก้ปัญหา

1. คำนวณกำลังของ y ล่วงหน้าเก็บใน vector
2. ลูป i สำหรับกำลังของ x (จนกว่า x^i >= bound)
3. ลูป j สำหรับกำลังของ y (จนกว่า x^i + y^j > bound)
4. เก็บผลรวมใน set (กรองซ้ำและเรียง)

ตัวอย่างโค้ด C++

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

void powerSum(int x, int y, int bound) {
    set<int> sumOfPowers;
    vector<int> powY;
    int i;
    
    powY.push_back(1);
    for (i = y; i < bound; i = i * y)
        powY.push_back(i);
    
    i = 0;
    while (true) {
        int powX = pow(x, i);
        if (powX >= bound) break;
        for (auto j = powY.begin(); j != powY.end(); ++j) {
            int num = powX + *j;
            if (num <= bound)
                sumOfPowers.insert(num);
            else
                break;
        }
        i++;
    }
    
    for (auto itr = sumOfPowers.begin(); itr != sumOfPowers.end(); itr++)
        cout << *itr << " ";
}

int main() {
    int x = 2, y = 3, bound = 25;
    cout << "Sum of powers of " << x << " and " << y << " less than " << bound << " are:\n";
    powerSum(x, y, bound);
    return 0;
}

ผลลัพธ์ (Output)

Sum of powers of 2 and 3 less than 25 are:
2 3 4 5 7 9 10 11 13 17 19 25