题目描述
Vanya 有一个天平，以及若干砝码，每个砝码的重量分别为 \(w^0, w^1, w^2, \dots, w^{100}\) 克，其中 \(w \ge 2\) 且每种重量的砝码只有一个。现在他想称量一个质量为 (m) 的物品，砝码可以放在天平的任意一个托盘上。问是否能够通过适当的放置使得天平平衡？
形式化地说，是否存在一种方案，将物品和一些砝码放在左盘，另一些砝码放在右盘，使得左右盘总质量相等？
输入格式
一行两个整数 \(w\) 和 \(m\)\((2 \le w \le 10^9\)，\(1 \le m \le 10^9\)）。
输出格式
如果可以称量，输出 "YES"，否则输出 "NO"。
解题思路
本题的关键在于砝码的重量是 \(w\) 的幂次，且每个幂次只有一个砝码。这种结构提示我们可以将问题转化为 \(w\)进制表示 的变形。
假设我们将物品放在左盘，那么平衡条件为：
其中 (L) 是放在左盘的砝码集合，(R) 是放在右盘的砝码集合。移项得：
因此，我们需要将 (m) 表示为 (w) 的幂次的带符号和，每个幂次最多出现一次，且系数只能是 (-1)、(0) 或 (1)（系数为 (1) 表示放在右盘，(-1) 表示放在左盘，(0) 表示不使用）。
这就相当于在 (w) 进制下，每个数位上的数字允许是 (-1,0,1)，而普通的 (w) 进制数字范围是 (0) 到 (w-1)。我们能否通过进位/借位的方式将 (m) 转换成这种“平衡三进制”的形式呢？
算法步骤
我们可以从最低位开始处理 \(m\)，每次考察当前最低位 \(m \bmod w\)：
- 如果 \(m \bmod w = 0\)：说明这一位是 \(0\)，可以直接除以 \(w\)去掉这一位。
- 如果 \((m - 1) \bmod w = 0\)：说明我们可以通过减去一个 \(1\)（相当于在左盘放一个该幂次的砝码）使得这一位变成 \(0\)，然后去掉这一位（即令 \(m = (m - 1) / w\)）。
- 如果 \((m + 1) \bmod w = 0\)：说明我们可以通过加上一个 \(1\)（相当于在右盘放一个该幂次的砝码）使得这一位变成 \(0\)，然后去掉这一位（即令 \(m = (m + 1) / w\)）。
- 如果以上条件都不满足，则无法用允许的系数表示这一位，输出
"NO"。
重复这个过程直到 \(m\) 变为 \(0\)。如果成功处理完所有位，则输出 "YES"。
时间复杂度
每次循环 \(m\) 至少除以 \(w\)，因此循环次数为 \(O(\log_w m)\)，在 \(w \ge 2\) 时最多约\(O(\log m)\)，非常快。
代码实现
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int N = 2e5 + 10, mod = 998244353, inf = LLONG_MAX;
ll n, w, m;
void solve() {cin >> w >> m;while (m) {if ((m - 1) % w == 0) { // 相当于加在m对面m--;} else if ((m + 1) % w == 0) { // 相当于加在mm++;} else if (m % w == 0) { // 这一位为0，什么都不放;} else {cout << "NO" << '\n';return;}m /= w; // 去掉已处理的最低位}cout << "YES" << '\n';
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _ = 1;// cin >> _;while (_--) {solve();}return 0;
}