CF#308に参加。
全完までの時間はかなり速かったけど、途中のWAとHackミスでちょっともったいない順位に。
http://codeforces.com/contest/552/problem/C
問題
整数W,Mが与えられる。
の整数をそれぞれ足し引きして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"); }
まとめ
わかってしまえば簡単な部類。