他の累乗での数値のC++表現

別の数の累乗で数を表す問題について話し合います。 xとyの2つの数字が与えられます。たとえば、yをxの累乗で表すことができるかどうかを判断する必要があります。たとえば、xの各累乗を1回使用できます。

Input: x = 4, y = 11
Output: true
Explanation: 4^2 - 4^1 - 4^0 = 11 Hence y can be represented in the power of x.

Input: x = 2, y = 19
Output: true
Explanation: 2^4 + 2^1 + 2^0 =19 Hence y can be represented in the power of x.

Input: x = 3, y = 14
Output: false
Explanation: 14 can be represented as 3^2 + 3^1 + 3^0 + 3^0 but we cannot use one term of power of x twice.

解決策を見つけるためのアプローチ

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）項を含めないかを表します-

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]かどうか、または解決策は存在しません。

例

#include <bits/stdc++.h>
using namespace std;
int main(){
   int x = 2, y = 19;
   // checking y divisibility till y>0
   while (y>0) {
      // If y-1 is divisible by x.
      if ((y - 1) % x == 0)
         y = (y - 1) / x;
        // If y is divisible by x.
      else if (y % x == 0)
         y = y / x;
         // If y+1 is divisible by x.
      else if ((y + 1) % x == 0)
         y = (y + 1) / x;
         // If no condition satisfies means
         // y cannot be represented in terms of power of x.
      else
         break;
   }
   if(y==0)
      cout<<"y can be represented in terms of the power of x.";
   else
      cout<<"y cannot be represented in terms of the power of x.";
   return 0;
}

出力

y can be represented in terms of the power of x.

結論

このチュートリアルでは、別の数の累乗の観点から数の表現が可能かどうかを確認する方法について説明しました。 yを使用して現在、先行、および後続の数の除算をチェックすることにより、この問題を解決するための簡単なアプローチについて説明しました。

また、C、Java、Pythonなどのプログラミング言語で実行できるこの問題のC++プログラムについても説明しました。このチュートリアルがお役に立てば幸いです。