C++で強力な整数（Powerful Integers）を求めるアルゴリズムと実装

強力な整数（Powerful Integers）とは

ここに3つの整数「a」「b」「limit」があるとします。この課題では、範囲 [a, limit] に含まれる数のうち、次の形式で表現できる数（強力な整数）をすべて出力します。

a^i + b^j（ただし i >= 0 かつ j >= 0）

具体例

入力：

a = 2
b = 5
limit = 10

出力：

[2, 3, 5, 6, 7, 9]

解説： 各指数 i と j の組み合わせごとに計算すると、以下のようになります。

　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

したがって、limit = 10 以内で表現できる強力な整数は [2, 3, 5, 6, 7, 9] となります。

この問題を解くためのアプローチ

この問題に対する最も基本的な解法は、総当たり（ブルートフォース）方式です。二重ループを使って limit を超えない範囲で各べき乗の組み合わせの和を求め、その結果をリストに追加していきます。

• 3つの整数「a」「b」「limit」を受け取ります。
• 関数 powerfulnumbers(int a, int b, int limit) がこれらの値を引数として受け取り、a^i + b^j（i >= 0、j >= 0）で表されるすべての強力な整数のリストを返します。
• limit までの範囲で二重ループを回し、各反復でべき乗の値を計算してその和を求めます。
• 得られた数が範囲 [a, limit] 内に収まっている場合は、重複を避けるために set（集合）に格納します。
• 最後に set を走査して結果を出力します。

なお、a または b が 1 の場合、べき乗の値が増加しないため無限ループに陥る恐れがあります。サンプルコードでは、このケースを break 文によって適切に処理しています。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
void powerfulNum(int a, int b, int limit) {
    set < int > 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;
    int b = 5;
    int limit = 10;
    powerfulNum(a, b, limit);
    return 0;
}

上記のコードを実行すると、次の出力が得られます。

出力

2 3 5 6 7 9

このように、範囲 2〜10 に含まれる強力な整数はすべて [2, 3, 5, 6, 7, 9] となります。set を使用することで重複が自動的に排除され、結果が昇順で出力される点も大きなメリットです。