kmjp's blog

競技プログラミング参加記です

Codeforces #308 Div2 C. Vanya and Scales

CF#308に参加。
全完までの時間はかなり速かったけど、途中のWAとHackミスでちょっともったいない順位に。
http://codeforces.com/contest/552/problem/C

問題

整数W,Mが与えられる。
 W^0, W^1, W^2, ..., W^100の整数をそれぞれ足し引きしてMを作れるか答えよ。
なお、各整数が使える数は0回か1回である。

解法

Wは2以上で、MはW^100よりずっと小さいのでWの上限はさほど気にしなくてよい。

M%Wが0か1ならMで割り、M%W==W-1なら1足してMで割る、という作業を繰り返しMが0に出来るか判定するだけ。
M%Wが0,1,W-1のどれにもならないなら条件を満たせない。

ll W,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>M;
	while(M) {
		if(M%W==0 || M%W==1){
			M/=W;
		}
		else if(M%W==W-1) {
			M=M/W+1;
		}
		else return _P("NO\n");
	}
	_P("YES\n");
	
}

まとめ

わかってしまえば簡単な部類。

広告を非表示にする