C++で指定した2つの数の累乗の和として表せるすべての整数を出力する方法

問題の概要

この問題では、2つの数 a と b、および整数 bound が与えられます。そのうえで、bound 以下の値のうち、a と b の累乗の和として表せるすべての値を出力することが求められます。

数式で表すと、以下の条件を満たす値をすべて求めることになります。

Bound >= ai + bj

問題を理解するための例

入力: a=2, b=3, bound=8
出力: 2 3 4 5 7

この例では、bound=8 以下で 2ⁱ + 3^j の形で表せる値は、2(=2⁰+3⁰)、3(=2¹+3⁰)、4(=2⁰+3¹)、5(=2¹+3¹)、7(=2²+3¹) となります。

解法のアプローチ

この問題を解くには、0 から始まる 2 つの変数 i と j を用いた二重ループ(ネストされたループ)を使用します。

• 外側のループの終了条件:xⁱ >= bound
• 内側のループの終了条件:xⁱ + y^j > bound

内側のループの各反復では、xⁱ + y^j の値を、該当するすべての値を格納するソート済みコンテナ(set)に追加していきます。そして最後に、コンテナ内のすべての値を出力します。

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++;
    }
    set<int>::iterator itr;
    for (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;
}

コードの解説

このプログラムのポイントは以下のとおりです。

• ベクトル powY には、y の累乗の値を bound 未満の範囲で事前に計算して格納します。
• 外側の while ループで x の累乗を 0 乗から順に生成し、bound 以上になった時点で処理を終了します。
• 内側の for ループで、x の累乗と y の各累乗の和を計算し、bound 以下であれば set に挿入します。
• set が重複の排除とソートを自動的に行うため、最後に要素を順に出力するだけで結果が得られます。

出力結果

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

この出力は、x=2、y=3、bound=25 の場合に、2ⁱ + 3^j の形で表せる bound 以下のすべての値を昇順に並べたものです。例えば、9 は 2³+3⁰=9、25 は 2⁴+3²=25 として表せます。