C++で数値を別の数の累乗の和・差として表現できるか判定する方法

問題概要

本記事では、ある数値を別の数値の累乗の組み合わせで表現できるかどうかを判定する問題について解説します。2つの整数 x と y が与えられ、x の各累乗はそれぞれ一度しか使用できないという条件のもとで、y を x の累乗の和と差で表せるかを判定します。

入力: x = 4, y = 11
出力: true
説明: 4^2 − 4^1 − 4^0 = 11 となるため、y は x の累乗で表現できます。

入力: x = 2, y = 19
出力: true
説明: 2^4 + 2^1 + 2^0 = 19 となるため、y は x の累乗で表現できます。

入力: x = 3, y = 14
出力: false
説明: 14 は 3^2 + 3^1 + 3^0 + 3^0 と表せますが、同じ累乗項を2回使うことはできません。

解法のアプローチ

19 を 2 の累乗で表した例をもとに考えると、次のような一般式を立てることができます。

c0(x^0) + c1(x^1) + c2(x^2) + c3(x^3) + … = y …(1)

ここで、係数 c0, c1, c2 などはそれぞれ -1、0、+1 のいずれかの値を取ります。-1 はその項を引くこと、+1 はその項を足すこと、0 はその項を含まないことを意味します。

(1)式を変形すると、

c1(x^1) + c2(x^2) + c3(x^3) + … = y − c0

x でくくり出すと、

c1(x^0) + c2(x^1) + c3(x^2) + … = (y − c0)/x …(2)

(1)式と(2)式を見比べると、元の問題と同じ構造の問題が再帰的に現れていることがわかります。解が存在するためには (y − ci) が x で割り切れる必要があり、ci は -1、0、+1 のいずれかでなければなりません。

したがって、y > 0 である間、「(y−1) % x == 0」「y % x == 0」「(y+1) % x == 0」のいずれかが成り立つかを順に確認していき、どれも満たさなくなった時点で解は存在しないと判断できます。この方法の計算量は、y を繰り返し x で割っていくため O(log_x y) と非常に効率的です。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int x = 2, y = 19;
    // y > 0 の間、割り切れるかどうかを確認
    while (y>0) {
        // y-1 が x で割り切れる場合
        if ((y - 1) % x == 0)
            y = (y - 1) / x;
        // y が x で割り切れる場合
        else if (y % x == 0)
            y = y / x;
        // y+1 が x で割り切れる場合
        else if ((y + 1) % x == 0)
            y = (y + 1) / x;
        // どの条件も満たさない場合、
        // y は x の累乗では表現できない
        else
            break;
    }
    if(y==0)
        cout<<"yはxの累乗で表現できます。";
    else
        cout<<"yはxの累乗で表現できません。";
    return 0;
}

出力結果

yはxの累乗で表現できます。

まとめ

本記事では、ある数値が別の数値の累乗の組み合わせで表現可能かどうかを判定する方法について解説しました。現在の値 y とその前後の値（y−1、y+1）が x で割り切れるかを順番に確認していく、シンプルかつ効率的なアプローチを紹介しました。

また、この問題を C++ で実装したサンプルコードも提示しました。同じロジックは C、Java、Python などの他のプログラミング言語でも容易に実装できます。このチュートリアルが皆さんの学習のお役に立てば幸いです。