In Tất Cả Số Nguyên Là Tổng Của Lũy Thừa Của Hai Số Cho Trước Trong C++

Trong bài toán này, chúng ta được cho hai số a và b và một giới hạn bound. In tất cả các giá trị nhỏ hơn bound là tổng của lũy thừa của a và b.

Bound >= a^i + b^j

Ví dụ để hiểu vấn đề:

Đầu vào: a=2, b=3, bound=8 → Đầu ra: 2 3 4 5 7

Để giải quyết, ta dùng vòng lặp lồng với hai biến i, j từ 0. Vòng ngoài điều kiện dừng a^i = bound, vòng trong a^i + b^j > bound. Mỗi lần lặp vòng trong, lưu giá trị a^i + b^j vào danh sách đã sắp xếp. Cuối cùng in tất cả giá trị.

Ví Dụ

Chương trình minh họa giải pháp:

#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 << "Tổng lũy thừa của " << x << " và " << y << " nhỏ hơn " << bound << " là:\n";
    powerSum(x, y, bound);
    return 0;
}

Đầu Ra

Tổng lũy thừa của 2 và 3 nhỏ hơn 25 là: 2 3 4 5 7 9 10 11 13 17 19 25