链接：https://ac.nowcoder.com/acm/contest/910/E

题目描述

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

输入描述:

第一行为一个整数T，代表有T组数据

接下来T行，每行有两个整数w,m (2 ≤ w ≤ 10^9, 1 ≤ m ≤ 10^9)。

输出描述:

如果能，输出YES，否则输出NO。

示例1

输入

2
3 7  
4 22

输出

YES
NO

备注:

对第一组样例，可以将重物和质量为3的砝码放到一个托盘中，质量为9和1的砝码放到另外一个托盘中。

第二组样例无论怎么搭配砝码和重物，也无法使天平两端达到平衡。

解题思路：

毫无头绪。。。看了大佬们ac的代码还是不懂，后来看了真正的题解才懂了(;´༎ຶД༎ຶ`)

看到w的0次方、1次方……n次方，可以想到w进制，把m转化为w进制，记为M，如果M加一些w的次方使得最后M的每位不是1就0，那么最后每位不是0就是1的M,就可以由一些w的次方组合成M,这就相当于天平的一边。

拿第一个样例来说吧：w=3，m=7，m写成3进制后即M=21，从末尾往前遍历，最末尾是1不用动，倒数第二位是2（2=3-1），所以M再加上3的1次方进位之后就变成了101，这样就可以知道天平的一边是3^2+1（即101（3）转换为10进制），另一边是7+3

但是需要注意的是如果M某位上的数字不是0也不是1时，只有当它是w-1才能从w的0次方、1次方……n次方选一个，然后进位，如果它不是w-1的话根据题目条件每个砝码只有一个，那么M就不能变成最终只含有1或0的数了，这样的话就要输出N0

综上，正解思路为：

将m转化成w进制，然后从小的位数开始遍历一遍如果为0或1不进行操作，如果为w-1则加上一个数使得当前位数变成0，如果为其他数着就可以直接输出NO，如果没有输出NO 则最后输出YES

 

ac代码：

#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <fstream>
#define  maxn 100
#define lowbit(x) (x&(-x))
typedef long long ll;
const ll mod=1e9+7;
using namespace std;
ll t,w,m,a[maxn];
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        memset(a,0,sizeof(a));//注意清空，否则第41行的代码可能会受影响，会wa掉
        bool flag=false;
        ll num=0;
        scanf("%lld %lld",&w,&m);
        while(m)//把m转换为w进制的数
        {
            a[num++]=m%w;
            m/=w;
        }
        for(ll i=0;i<num;i++)
        {
            if(a[i]==0 || a[i]==1) continue;
            else if(a[i]==w-1)//选择一个w的i次方模拟进位
            {
                ll index=i+1;
                ll carry=1;//进1
                a[i]=0;
                while(carry)
                {
                    a[index]+=carry;
                    carry=a[index]/w;
                    a[index]%=w;
                    index++;
                    if(index > num) num=index;//进位之后总位数变大
                }
            }
            else
            {
                flag=true;
                break;
            }
        }
        if(flag) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}