/*
Runtime: 0 ms, faster than 100.00% of Java online submissions for Divisor Game.
Memory Usage: 32.8 MB, less than 13.33% of Java online submissions for Divisor Game.
*/
class Solution {
    public boolean divisorGame(int N) {
        if (N == 0) return true;

        byte[] cache = new byte[N + 1];
        return wins(N, cache) == +1;
    }

    private byte wins(int n, byte[] cache) {
        if (n == 1) return -1;
        if (cache[n] != 0) return cache[n];

        byte result = -1;
        for (int x = 1; x * x <= n; x++ ) {
            if (n % x == 0) {
                if (wins(n - x, cache) == -1) {
                    result = +1;
                    break;
                }

                int y = n / x;
                if (y < n && wins(n - y, cache) == -1) {
                    result = +1;
                    break;
                }
            }
        }

        cache[n] = result;
        return result;
    }
}