Codeforces 552.C Vanya and Scales 【思维】

英文传送门          中文传送门

很好的一道思维题，巧妙的利用到了进制的思想
    =0,1,-1  分别表示不选择这个砝码，放在重物的另一边，放在重物一起
我们可以通过来枚举  来判断等式是否成立

如果   则等式为   等式右边可以被w整除，想要等式成立，那么m也必须被w整除

如果  则等式为 想要等式成立，那么（m-w^0）=（m-1）也必须被w整除

如果  则等式为 想要等式成立，那么（m+w^0）=（m+1）也必须被w整除

如果三种情况都不满足，则说明无解。
如果上述等式满足，我们将等式两边都除以 w ,将等式化简，保证我们当前判断w的幂为0，然后继续判断。

特殊情况：当 w <=3 ，无论 m 等于多少，等式必然成立 。（剪枝）
代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int w, m, t;
    scanf("%d", &t);
    while(t--) {
        int flag = 1;
        scanf("%d %d", &w, &m);
        if(w <= 3) {
            puts("YES");
            continue;
        }
        while(m && flag) {
            if(m % w == 0) {    ///系数为0
                m /= w;
            } else if((m + 1) % w == 0) {   ///系数为-1
                m = (m + 1) / w;
            } else if((m - 1) % w == 0) {   ///系数为1
                m = (m - 1) / w;
            } else {
                flag = 0;                   ///等式不成立
            }
        }
        puts(flag ? "YES" : "NO");
    }
    return 0;
}