CF552C Vanya and Scales 题解
紊莫
·
·
题解
题意
# 分析
如果满足题意，则**当前的** $m$，$m-1$，$m+1$ 中必有一个能被 $w$ 整除的数。
因为 $p_0w^0$ 这一项的取值只有 $1,0,-1$ 三种可能。
于是可以考虑类似迭代的方式去分解 $m$。
巧妙地发现每个 $m$ 都满足以上性质。
一旦在任何一次循环中不满足条件就立刻退出即可。
# 代码
```cpp
int w=read(),m=read();
while(m)
{
if(m%w==0){
m/=w;
}
else if((m-1)%w==0){
m=(m-1)/w;
}
else if((m+1)%w==0){
m=(m+1)/w;
}
else{
puts("NO");
return 0;
}
}
puts("YES");
```
相当于一次次的分解下去，如果最后为 0 就证明两者相等了。
另外可以特判一下，如果 $w\le3$ 就可以直接输出，因为已知这个范围内可以拼出所有符合条件的 $m$。