Given an $N\times M$ board and a starting location $(x,y)$ with $1\le x\le N$ and $1\le y\le M$, Alice and Bob play the following game: Alice begins by placing a pawn on square $(x,y)$, then Bob moves the pawn to an adjacent square of the four potential neighboring squares (diagonals don't count) and removes the square the pawn left from the board. Alice makes the next move, and they alternate until a player has no possible move and loses the game.

Since this is a game obeying Zermalo's theorem, given $N\times M$ and $(x,y)$ either Alice can force a win, or Bob can force a win. Call $(x,y)$ an "A" square for the board if Alice can force a win, and "B" if Bob can force a win.

To complicate the game, we can remove some of the squares in the board before the game begins, in the following manner. Fix two prime numbers $p,q$, and label each square in the board with a number, such that square $(i,j)$ is labelled $p^i+q^j$ (recall that indexing starts from 1, not 0). Now, pick a prime number $s$, and remove from the board all the squares whose label is divisible by $s$.

For example, it can be seen that for $N=M=3$, the board is

A B A
B A B
A B A

But if we choose $p=19, q=2, s=5$, as $19^2+2^2=365$ which is divisible by 5 the board becomes

B B B
B # B
B B B

With # denoting the missign square in the middle.

Given a board size $N\times M$, two primes $p,q$ and a set $S$ of prime numbers, for each $s\in S$ we can count the number of "A" and "B" squares in the board (we don't count "#"). We can then sum those values over all the possible $s\in S$.

For example, for $N=M=3$ and $p=19, q=2$ and $S = [2,3,5,7,11]$ we have a total of $16$ "A" and $19$ "B".

Your goal: Find the total number of "A" and "B" for $N=M=157$, $p=419, q=211$ and $S$ being the set of all prime numbers lower than 100.

A bonus "*" will be given for finding the total number of "A" and "B" for $N=M=1557$, $p=419, q=211$ and $S$ being the set of all prime numbers lower than 500.

Solution

Solvers