C++ 用其他数的幂表示数字
c++server side programmingprogramming
讨论用另一个数的幂表示数字的问题。我们给出两个数字，x 和 y。我们需要判断 y 是否可以用 x 的幂表示，其中 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，但我们不能使用 x 的幂的一项两次。
寻找解决方案的方法
通过检查 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;
// 检查 y 可整除性直到 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 等编程语言来完成。我们希望您觉得本教程有用。
