Thảo luận về vấn đề biểu diễn một số theo lũy thừa của một số khác. Chúng ta được cung cấp hai số, x và y. Chúng ta cần biết liệu y có thể được biểu diễn dưới dạng lũy thừa của x trong đó mỗi lũy thừa của x có thể được sử dụng một lần hay không, chẳng hạn
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.
Phương pháp tiếp cận để tìm giải pháp
Từ việc xem xét ví dụ về cách 19 được biểu diễn dưới dạng lũy thừa của 2, chúng ta có thể hình thành một phương trình -
c0(x^0) + c1(x^1) + c2(x^2) + c3(x^3) + … = y ….(1),
Trong đó c0, c1, c2 có thể là -1, 0, +1 để biểu thị liệu (-1) số hạng bị trừ, (+1) số hạng được thêm vào, (0) số hạng không được đưa vào -
c1(x^1) + c2(x^2) + c3(x^3) + … = y - c0,
Lấy x làm thông thường,
c1(x^0) + c2(x^1) + c3(x^2) + … = (y - c0)/x ….(2),
Từ eq (1) và (2), chúng ta có thể biểu diễn lại số theo cách và để một nghiệm tồn tại (y - Ci) nên chia hết cho x và Ci chỉ có thể chứa -1, 0 và +1.
Vì vậy, cuối cùng chúng ta cần kiểm tra cho đến khi y> 0 xem [(y-1)% x ==0] hoặc [(y)% x ==0] hoặc [(y + 1)% x ==0] hoặc liệu a giải pháp không tồn tại.
Ví dụ
#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;
} Đầu ra
y can be represented in terms of the power of x.
Kết luận
Trong hướng dẫn này, chúng ta đã thảo luận về cách kiểm tra xem biểu diễn của một số có khả thi theo lũy thừa của một số khác hay không. Chúng tôi đã thảo luận về một cách tiếp cận đơn giản để giải quyết vấn đề này bằng cách kiểm tra khả năng chia hết số hiện tại, số trước và số tiếp theo với y.
Chúng tôi cũng đã thảo luận về chương trình C ++ cho vấn đề này mà chúng tôi có thể làm với các ngôn ngữ lập trình như C, Java, Python, v.v. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.