407867: GYM102911 C Chocolate Game: Love is War

Alice is madly in love with Bob and she hopes to impress him by beating him in yet another chocolate game.

• The game begins with two piles of chocolate cookies, one on the left and one on the right. Alice and Bob will take turns.
• On each player's turn, they must choose exactly one of the piles, and eat some positive number of cookies from it such that the number of cookies remaining is a positive divisor of the previous pile size. More formally, if there are $$$n$$$ cookies in the chosen pile, then they can only eat $$$k$$$ cookies from that pile if $$$k$$$ is a positive integer and $$$n-k$$$ is a positive divisor of $$$n$$$.
• The player with no valid move (the person whose turn it is when both piles are size $$$1$$$) is declared the loser.
• Alice always goes first.

Alice and Bob are supergenius, perfectly rational grandmaster prodigies who always make the optimal move in any game they play. Alice considers a game to be WINNABLE if there is some strategy she can follow so that she is guaranteed to win no matter what Bob does (so long as Alice plays correctly). Alice considers a game UNWINNABLE if Bob has a strategy he can follow so that she is guaranteed to lose no matter what she does (so long as Bob is playing correctly).

Bob is madly in love with Cindy, so he places $$$M$$$ cookies in the left pile and $$$N$$$ cookies in the right pile, since $$$M$$$ and $$$N$$$ are Cindy's favorite numbers.

Cindy is madly in love with Alice, so she will rig the game such that it will be WINNABLE for Alice, by taking some number of cookies from each pile. So that Bob does not notice the changes, she can only take at most $$$X$$$ cookies from the left pile, and at most $$$Y$$$ cookies from the right pile. Cindy can also choose not to take any cookies from either pile. You are also assured that $$$X < M$$$ and $$$Y < N$$$.

How many different ways can Cindy rig the game in Alice's favor? Formally, count the number of ordered pairs of integers $$$(x,y)$$$ such that $$$0 \leq x \leq X$$$ and $$$0 \leq y \leq Y$$$, and a game that initially begins with piles of size $$$M-x$$$ and $$$N-y$$$ is WINNABLE for Alice.

Input consists of a single line with four space-separated integers $$$M$$$, $$$N$$$, $$$X$$$, and $$$Y$$$.

Output a single integer, the number of different ways that Cindy can rig the game in Alice's favor.

It is recommended that Python users submit to PyPy for this problem.

$$$0 \leq X < M$$$

$$$0 \leq Y < N$$$

Subtask 1 (30 points):

$$$1 \leq M,N \leq 10$$$

Subtask 2 (20 points):

$$$1 \leq M,N \leq 100$$$

Subtask 3 (20 points):

$$$1 \leq M,N \leq 1000$$$

Subtask 4 (15 points):

$$$1 \leq M,N \leq 5\cdot 10^4$$$

Subtask 5 (15 points):

$$$1 \leq M,N \leq 5\cdot 10^6$$$

5 10 1 2

4

10 10 9 9

66

In the first sample test case, suppose Cindy took $$$x=0$$$ cookies from the left pile and $$$y=1$$$ cookies from the right pile. Then, the game will have pile sizes $$$5$$$ and $$$9$$$, which we can show is WINNABLE for Alice.

First, she eats $$$6$$$ cookies from the right pile, which she can do because $$$9-6 = 3$$$ and $$$3$$$ is a positive divisor of $$$9$$$.

Now, the pile sizes are $$$5$$$ and $$$3$$$. If Bob eats from the left pile, his only choice is to eat $$$4$$$ cookies from it; then, Alice eats $$$2$$$ cookies from the right pile. If Bob eats from the right pile, his only choice is to eat $$$2$$$ cookies it; then, Alice eats $$$4$$$ cookies from the left pile.

In either case, there is only $$$1$$$ cookie left in each pile on Bob's turn, so he loses.

We can show that the full list of solutions are $$$(0,0)$$$, $$$(0,1)$$$, $$$(0,2)$$$, and $$$(1,2)$$$ for the first sample test case.