Codeforces Round #308 Div2 C: Vanya and Scales

問題

codeforces.com

解法

天秤が釣り合う時、となる。この時、と書ける。
mをwで割り切れる限り割り続けると、またはというように、あまり1か-1になる。つまりmがwで割り切れる時は割り続け、割り切れなくなったら1を足すか引くかして、それでも割り切れなかったら釣り合わない、最終的にm=1となる時は釣り合う、ということが出来る。

コード

import java.util.Scanner;

public class Main {

	public void solve() {
		Scanner sc = new Scanner(System.in);
		long W = sc.nextLong();
		long M = sc.nextLong();
		sc.close();
		int cur = 0;
		while (Math.pow(W, cur) < M) {
			cur++;
		}
		if (Math.pow(W, cur) == M) {
			System.out.println("YES");
			return;
		}

		if (saiki(W, M)) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}

	}

	private boolean saiki(long W, long M) {
		if (M == 1) {
			return true;
		}
		if (M % W == 0) {
			return saiki(W, M / W);
		} else if ((M - 1) % W == 0) {
			return saiki(W, (M - 1) / W);
		} else if ((M + 1) % W == 0) {
			return saiki(W, (M + 1) / W);
		}
		return false;
	}

	public static void main(String[] args) {
		new Main().solve();
	}
}