Cho x, y. Kiểm tra y có thể biểu diễn dưới dạng tổ hợp các lũy thừa của x (mỗi lũy thừa dùng tối đa 1 lần, hệ số -1, 0, +1). Ví dụ:
Input: x=4, y=11 → true (4² - 4¹ - 4⁰ = 11) Input: x=2, y=19 → true (2⁴ + 2¹ + 2⁰ = 19) Input: x=3, y=14 → false (cần 3⁰ 2 lần)
Cách tiếp cận
Từ phương trình: c₀x⁰ + c₁x¹ + ... = y với cᵢ ∈ {-1,0,1}. Rút gọn: (y - c₀) % x == 0. Lặp: nếu (y-1)%x==0 thì y=(y-1)/x; nếu y%x==0 thì y/=x; nếu (y+1)%x==0 thì y=(y+1)/x; ngưng khi không thỏa mãn. Nếu cuối cùng y==0 → true.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main() {
int x = 2, y = 19;
while (y > 0) {
if ((y - 1) % x == 0) y = (y - 1) / x;
else if (y % x == 0) y = y / x;
else if ((y + 1) % x == 0) y = (y + 1) / 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;
}
Kết quả
y can be represented in terms of the power of x.
Kết luận
Kiểm tra biểu diễn số bằng lũy thừa của số khác (hệ số -1,0,1) bằng thuật toán chia lặp. Code C++ O(logₓ y).