Google Code Jam '10 Round 1A Problem C - Number Game

Points: 20 (partial)

Time limit: 90.0s

Memory limit: 1G

Problem types

Arya and Bran are playing a game. Initially, two positive integers $A$ ~A~ and $B$ ~B~ are written on a blackboard. The players take turns, starting with Arya. On his or her turn, a player can replace $A$ ~A~ with $A - k \cdot B$ ~A - k \cdot B~ for any positive integer $k$ ~k~, or replace $B$ ~B~ with $B - k \cdot A$ ~B - k \cdot A~ for any positive integer $k$ ~k~. The first person to make one of the numbers drop to zero or below loses.

For example, if the numbers are initially $(12, 51)$ ~(12, 51)~, the game might progress as follows:

Arya replaces $51$ ~51~ with $51 - 3*12 = 15$ ~51 - 3*12 = 15~, leaving $(12, 15)$ ~(12, 15)~ on the blackboard.
Bran replaces $15$ ~15~ with $15 - 1*12 = 3$ ~15 - 1*12 = 3~, leaving $(12, 3)$ ~(12, 3)~ on the blackboard.
Arya replaces $12$ ~12~ with $12 - 3*3 = 3$ ~12 - 3*3 = 3~, leaving $(3, 3)$ ~(3, 3)~ on the blackboard.
Bran replaces one $3$ ~3~ with $3 - 1*3 = 0$ ~3 - 1*3 = 0~, and loses.

We will say $(A, B)$ ~(A, B)~ is a winning position if Arya can always win a game that starts with $(A, B)$ ~(A, B)~ on the blackboard, no matter what Bran does.

Given four integers $A_{1}$ ~A_{1}~, $A_{2}$ ~A_{2}~, $B_{1}$ ~B_{1}~, $B_{2}$ ~B_{2}~, count how many winning positions $(A, B)$ ~(A, B)~ there are with $A_{1} \le A \le A_{2}$ ~A_{1} \le A \le A_{2}~ and $B_{1} \le B \le B_{2}$ ~B_{1} \le B \le B_{2}~.

Input Specification

The first line of the input gives the number of test cases, $T$ ~T~. $T$ ~T~ test cases follow, one per line. Each line contains the four integers $A_{1}$ ~A_{1}~, $A_{2}$ ~A_{2}~, $B_{1}$ ~B_{1}~, $B_{2}$ ~B_{2}~, separated by spaces.

Output Specification

For each test case, output one line containing Case #x: y, where $x$ ~x~ is the case number (starting from 1), and $y$ ~y~ is the number of winning positions $(A, B)$ ~(A, B)~ with $A_{1} \le A \le A_{2}$ ~A_{1} \le A \le A_{2}~ and $B_{1} \le B \le B_{2}$ ~B_{1} \le B \le B_{2}~.

Limits

Memory limit: 1 GB.

$1 \le T \le 100$ ~1 \le T \le 100~.

$1 \le A_{1} \le A_{2} \le 1\,000\,000$ ~1 \le A_{1} \le A_{2} \le 1\,000\,000~.

$1 \le B_{1} \le B_{2} \le 1\,000\,000$ ~1 \le B_{1} \le B_{2} \le 1\,000\,000~.

Small Dataset

Time limit: 30 seconds.

$A_{2} - A_{1} \le 30$ ~A_{2} - A_{1} \le 30~.

$B_{2} - B_{1} \le 30$ ~B_{2} - B_{1} \le 30~.

Large Dataset

Time limit: 90 seconds.

$A_{2} - A_{1} \le 999\,999$ ~A_{2} - A_{1} \le 999\,999~.

$B_{2} - B_{1} \le 999\,999$ ~B_{2} - B_{1} \le 999\,999~.

No additional constraints.

Sample Input

Sample Output

Case #1: 0
Case #2: 1
Case #3: 20

Note

This problem has different time limits for different batches. If you exceed the Time Limit for any batch, the judge will incorrectly display >90.000s regardless of the actual time taken. Refer to the Limits section for batch-specific time limits.

Comments

There are no comments at the moment.