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

3つの整数 a、b、x が与えられたとき、a^b の値に最も近い x の倍数を求めることを考えます。

例えば、a = 5、b = 4、x = 3 の場合を考えてみましょう。5⁴ = 625 ですが、625 に最も近い 3 の倍数は 624 となります。これが求めるべき出力です。

解法のアプローチ

この問題は非常にシンプルで、以下の手順に従うことで解決できます。

• まず num = a^b を計算します。
• 次に f = floor(num / x)(num を x で割った値の切り捨て)を求めます。
• 左側(小さい側)で最も近い候補は cl = x × f、右側(大きい側)の候補は cr = x × (f + 1) となります。
• 最後に、num − cl と cr − num のうち小さい方を採用すれば、それが最も近い倍数です。

C++での実装例

#include <iostream>
#include <cmath>
using namespace std;
long long getClosest(int a, int b, int x) {
    long long num = pow(a, b);
    int f = floor(num / x);
    long long cl = x * f;
    long long cr = x * (f + 1);
    if ((num - cl) < (cr - num))
        return cl;
    else
        return cr;
}
int main() {
    int a = 5, b = 4, x = 3;
    cout << "Find closest element: " << getClosest(a, b, x);
}

実行結果

Find closest element: 624

このように、べき乗の計算結果に対して商の切り捨て値を使えば、左右両隣の倍数を簡単に特定でき、距離を比較するだけで最も近い倍数を効率的に求めることができます。なお、大きな指数を扱う場合はオーバーフローに注意し、必要に応じて long long 型などの十分な桁数を持つデータ型を使用することをおすすめします。