C++ 表示一个数的其他幂
讨论用另一个数的幂表示一个数的问题。我们有两个数字，x和y。我们需要判断y是否可以用x的幂表示，其中x的每个幂都可以使用一次，例如
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.
寻找解决方案的方法
通过检查如何用2的幂表示19的例子，我们可以形成一个方程-
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),
从eq(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) {
//如果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检查当前、前一个和后一个数的可整性。
我们还讨论了针对这个问题的C++程序，我们可以使用C、Java、Python等编程语言来解决这个问题。我们希望本教程对您有所帮助。