链接：https://ac.nowcoder.com/acm/contest/910/E
来源：牛客网

题目描述
现在有很多砝码，质量为w的0次方、1次方……n次方，每个砝码都只有一个。还有一个天平，可以在两端放置砝码和重物。现在要用这些砝码搭配出相等于重物的质量m，也可以把若干个砝码和重物一起放在天平的一侧，来平衡这个天平。

首先我的解法比较骚气，类似模拟，所以（因果关系？）先把w=2的情况特判掉（不要问我w=2为什么一定成立）。
然后我们确定一个边界值a[n]，使得a[n]恰好大于等于m。
其中a[i]为第i个砝码的质量，b[i]为前i个砝码的质量和。

	int cnt=1;
	while(a[cnt]<m){
	    a[++cnt]=a[cnt-1]*w;
	    b[cnt]=b[cnt-1]+a[cnt];
	}

通过等比数列求和可得w>=3时 b[n]<=a[n+1]/2
因此边界值之后的砝码一定是我们用不到的，因为在w大于等于三时一定有a[n+1]>=b[n]*2，因为b[n]>m，所以也就是a[n+1]-b[n]>m，因此就算把之前所有的砝码减去也无法到达m，再之后的砝码亦然。

然后我们从边界值开始逆序判断：对于当前这个砝码，我是否需要添加。
设我当前位置为pos，砝码为第cnt个，则前（cnt-1）个砝码所能控制的最大范围就是b[cnt-1]。
我们对当前砝码进行判断：
如果我与m的距离小于等于于b[cnt-1]，则无需 加上/减去 砝码，因为我就算用上接下来所有砝码也无法平衡。
如图：如果pos加上A[cnt]，那与m的距离显然会大于b[cnt-1]。所以该操作肯定是非法的，无需执行。

而如果这个操作能让pos与m的距离小于等于b[cnt-1]，那就说明当前的pos与m的距离在b[cnt-1]的控制范围外（想一想，为什么？），图示如下：

所以我们必须进行该操作。
这时，如果两种情况皆不合理，也就是m在中间，那我就算加不加当前砝码都会与其距离大于b[cnt-1]，这就是无解的情况，那我们的while就会停下来等死（挂机到a[1]自动退出）hhh。

int flag=0;
long long pos=0;
while(cnt){
    if(abs(pos+a[cnt]-m)<=b[cnt-1]){//如果加上该砝码能使我们进入b[cnt-1]的控制范围
        pos+=a[cnt];
    }
    else if(abs(pos-a[cnt]-m)<=b[cnt-1]){//如果减去该砝码能使我们进入b[cnt-1]的控制范围
        pos-=a[cnt];
    }
    if(pos==m){//判断是否已经等于m
        flag=1;
        break;
    }
    cnt--;
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
long long w,m;
long long a[233];//记录第i个砝码的质量
long long b[233];//记录前i个砝码的质量和
int main()
{
    int t;
    cin>>t;
    while(t--){
        scanf("%lld%lld",&w,&m);
        if(w==2)//巧妙绝伦的特判
        {
            cout<<"YES"<<endl;
            continue;
        }
        a[1]=1;
        b[1]=1;
        int cnt=1;
        while(a[cnt]<m){
            a[++cnt]=a[cnt-1]*w;
            b[cnt]=b[cnt-1]+a[cnt];
        }
        int flag=0;
        long long pos=0;
        while(cnt){
            if(abs(pos+a[cnt]-m)<=b[cnt-1]){
                pos+=a[cnt];
            }
            else if(abs(pos-a[cnt]-m)<=b[cnt-1]){
                pos-=a[cnt];
            }
            if(pos==m){
                flag=1;
                break;
            }
            cnt--;
        }
        if(flag)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
 
    }
    return 0;
}