codeforces C. Vanya and Scales

简介:
 C. Vanya and Scales

Vanya has a scales for weighing loads and weights of masses w0, w1, w2, ..., w100 grams where w is some integer not less than 2(exactly one weight of each nominal value). Vanya wonders whether he can weight an item with mass m using the given weights, if the weights can be put on both pans of the scales. Formally speaking, your task is to determine whether it is possible to place an item of mass m and some weights on the left pan of the scales, and some weights on the right pan of the scales so that the pans of the scales were in balance.

Input

The first line contains two integers w, m (2 ≤ w ≤ 109, 1 ≤ m ≤ 109) — the number defining the masses of the weights and the mass of the item.

Output

Print word 'YES' if the item can be weighted and 'NO' if it cannot.

Sample test(s)
input
3 7
output
YES
input
100 99
output
YES
input
100 50
output
NO
Note

Note to the first sample test. One pan can have an item of mass 7 and a weight of mass 3, and the second pan can have two weights of masses 9 and 1, correspondingly. Then 7 + 3 = 9 + 1.

Note to the second sample test. One pan of the scales can have an item of mass 99 and the weight of mass 1, and the second pan can have the weight of mass 100.

Note to the third sample test. It is impossible to measure the weight of the item in the manner described in the input.

 

题意:给定两个数,m和w,现有w^0, w^1, w^2...w^100各一个重量的mass, 用其中的一些mass,时候能称出m的重量。

也就是有如下图的式子:

复制代码
#include<iostream> 
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int main(){
    int m, w;
    cin>>w>>m;
    while(m){
        if(!((m-1)%w)) m--;
        else if(!((m+1)%w)) m++;
        else if(m%w){
            cout<<"NO"<<endl;
            return 0;
        }
        m/=w;
    }
    cout<<"YES"<<endl;
    return 0;
}









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/4598396.html,如需转载请自行联系原作者
目录
相关文章
codeforces 312
A. Whose sentence is it?
47 0
codeforces 322 B Ciel and Flowers
有红绿蓝三种颜色的画,每种拿三朵可以组成一束花,或者各拿一朵组成花束,告诉你每种花的数目,求出可能组成最多的花束。 如果你的代码过不了,考虑一下 8 8 9这种组合。 因为数据量很大,我的思想就是局部和总体采用不同的策略。
47 0
|
5月前
codeforces
【6月更文挑战第10天】
30 0
codeforces 322 A Ciel and Dancing
有n个男孩和m个女孩,他们要结对跳舞,每对要有一个女孩和一个男孩,而且其中一个要求之前没有和其他人结对,求出最大可以结多少对。
35 0
codeforces 304A. Pythagorean Theorem II
给你一个n,计算出1 ≤ a ≤ b ≤ c ≤ n.使得由abc构成的三角形满足勾股定理,c为斜边。 没有简单的方法,直接爆力,但是要注意,有些abc满足勾股定理的表达式,但不一定是三角形,所以要判断一下,根据三角形三边的性质,两边之和大于第三边,两边之差小于第三边。
58 0
|
C++
codeforces 305 C. Ivan and Powers of Two
我的思路是这样的,由2^a+2^a = 2^(a+1)可知,如果有两个连续的数a,我们可以把他们合并为a+1放入集合中,使集合中没有重复的数,我可以用stl里的set。如果想要满足题目中的要求,集合中必须有最大那个数个元素,缺多少就可以计算出来了。
29 0
C - Rumor CodeForces - 893C
C - Rumor CodeForces - 893C
87 0