C++で a^b に最も近い x の倍数を求める方法

3つの値 a、b、x が与えられたとき、a^b に最も近い x の倍数を求める問題を考えてみましょう。例えば、x = 4、a = 3、b = 3 の場合、3³ = 27 に最も近い x の倍数は 28 となるため、出力は 28 になります。

解法のアプローチ

考え方はシンプルで、以下の条件に従って処理を分岐させます。

• b < 0 かつ a = 1 の場合： a^b は 1 になるため、x に最も近い倍数は 0 または x となります。

• b < 0 かつ a > 1 の場合： a^b は 1 より小さくなるため、x に最も近い倍数は 0 となります。

• b > 0 の場合： まず a^b を計算します。次に mul = a^b / x（整数部分）とすると、x の倍数として最も近いのは mul × x または (mul + 1) × x のどちらかです。

C++による実装例

#include<iostream>
#include<cmath>
using namespace std;

void findMultiple(int a, int b, int x) {
    cout << "最も近い倍数: ";
    if (b < 0) {
        if (a == 1 && x == 1)
            cout << "1";
        else
            cout << "0";
        return;
    }
    int mul = pow(a, b);
    int ans = mul / x;
    int ans1 = x * ans;
    int ans2 = x * (ans + 1);
    if ((mul - ans1) <= (ans2 - mul)) {
        cout << ans1;
    }
    else {
        cout << ans2;
    }
}

int main() {
    int a = 3, b = 3, x = 4;
    findMultiple(a, b, x);
    return 0;
}

実行結果

最も近い倍数: 28

コードの解説

このプログラムの流れを順に見ていきましょう。

1. まず、b が負の場合を判定します。a = 1 で x = 1 のときは結果が 1、それ以外は 0 を出力して処理を終了します。

2. b が正の場合は pow(a, b) で a^b を計算し、それを x で割った商（整数部分）を求めます。

3. 商に x を掛けた値（ans1）と、商に 1 を足してから x を掛けた値（ans2）のうち、a^b との差が小さい方を答えとして出力します。

この例では 3³ = 27、27 ÷ 4 の商は 6 なので、候補は 6 × 4 = 24 と 7 × 4 = 28 の2つです。27 との差を比較すると 28 の方が近いため、28 が出力されます。

なお、pow 関数は浮動小数点数を返すため、大きな指数を扱う場合はオーバーフローや精度の問題に注意が必要です。実用的なコードでは、繰り返し乗算によるべき乗計算や long long 型の使用を検討するとよいでしょう。